Member Avatar for cezarjont

is min heap different from max heap...?
can you please show me examples...?

  • 5 Contributors
  • 7 Replies
  • 6K Views
  • 3 Years Discussion Span
  • Latest Post Latest Post by Narue

Dani AI

Generated

At a high level, both min-heaps and max-heaps are the same data structure: a complete binary tree stored in an array. The only difference is the ordering rule at each node. For a min-heap, each parent’s key is not greater than its children; for a max-heap, each parent’s key is not less than its children. Heaps are ideal for priority queues (e.g., a min-heap for Dijkstra’s shortest path, a max-heap for selecting the largest items).

If you are implementing this in C with a 0-based array, the index math is:

  • left(i) = 2i + 1, right(i) = 2i + 2, parent(i) = (i - 1) / 2
  • Build in O(n) by sifting down from the last parent to the root.
  • Push/pop are O(log n) via sift-up/sift-down.

A comparator-based outline (works for both min and max by changing cmp):

# cmp(x, y) returns true if x should come before y (use x < y for min-heap, x > y for max-heap)

sift_down(a, i, n, cmp):
    for:
        l = 2*i + 1; r = l + 1; m = i
        if l < n and cmp(a[l], a[m]): m = l
        if r < n and cmp(a[r], a[m]): m = r
        if m == i: break
        swap(a[i], a[m]); i = m

build_heap(a, n, cmp):
    for i from (n/2 - 1) down to 0:
        sift_down(a, i, n, cmp)

pop_top(a, n, cmp):
    swap(a[0], a[n-1]); n = n - 1
    sift_down(a, 0, n, cmp)

Common pitfall: when popping, swap with index n-1 (the last valid element), not n.

For deeper background, see MIT’s lecture notes on heaps and heapsort (MIT OCW). For library-supported heaps, the C++ comparator pattern is documented at cppreference: make_heap/pop_heap/push_heap.

Recommended Answers

All 7 Replies

Member Avatar for Ravalon

is min heap different from max heap...?

Yes. :) A min heap uses ascending priority where the smallest item is the first to be popped from the heap. A max heap uses descending priority where the largest item is the first to be popped. You can read more about heaps here. Oh, the C++ heap functions in <algorithm> assume a max heap. :)

#include <algorithm>
#include <cstdlib>
#include <iostream>


int main()
{
  using namespace std;

  int heap[10];

  for ( int i = 0; i < 10; i++ )
    heap[i] = rand() % 100;

  // Build a max heap
  make_heap( heap, heap + 10 );

  // Prove that it's a max heap
  for ( int n = 10; n > 0; n-- ) {
    for ( int i = 0; i < n; i++ )
      cout << heap[i] << ' ';
    pop_heap( heap, heap + n );
    cout << '\n';
  }

  return 0;
}

You can turn it into a min heap with some clever functional magic. ;)

#include <algorithm>
#include <functional>
#include <cstdlib>
#include <iostream>


int main()
{
  using namespace std;

  int heap[10];

  for ( int i = 0; i < 10; i++ )
    heap[i] = rand() % 100;

  // Build a max heap
  make_heap( heap, heap + 10, greater<int>() );

  // Prove that it's a max heap
  for ( int n = 10; n > 0; n-- ) {
    for ( int i = 0; i < n; i++ )
      cout << heap[i] << ' ';
    pop_heap( heap, heap + n, greater<int>() );
    cout << '\n';
  }

  return 0;
}
Member Avatar for cezarjont

thnx... but i can't really understand it... i only know turbo c... not c++...

Member Avatar for Ravalon

thnx... but i can't really understand it... i only know turbo c... not c++...

But I don't wanna write a heap in C just for an example. :cry: Okay okay, here is a simple example in C for a max heap. :)

#include <stdlib.h>


#define CHILD(node) ((node) * 2 + 1)


static void heapify( int a[], int i, int n )
{
  /* Heapify an unknown number of subtrees */
  while ( CHILD( i ) < n ) {
    int child = CHILD( i );

    /* Pick the larger of the two children */
    if ( child + 1 < n && a[child] < a[child + 1] )
      ++child;

    /* Move the largest node to the root */
    if ( a[i] < a[child] ) {
      int temp = a[i];
      a[i] = a[child];
      a[child] = temp;
    }

    /* Move to the next node */
    ++i;
  }
}


void make_heap( int a[], int n )
{
  int i = n / 2;

  while ( i-- > 0 )
    heapify( a, i, n );
}


void pop_heap( int heap[], int n )
{
  int temp = heap[0];
  heap[0] = heap[n];
  heap[n] = temp;
  heapify( heap, 0, n );
}


int main( void )
{
  int heap[10];
  int i;
  int n;

  for ( i = 0; i < 10; i++ )
    heap[i] = rand() % 100;

  /* Build a max heap */
  make_heap( heap, 10 );

  /* Prove that it's a max heap */
  for ( n = 10; n >= 0; n-- ) {
    printf( "%d ", heap[0] );
    pop_heap( heap, n );
  }

  putchar( '\n' );

  return 0;
}

And a min heap.

#include <stdlib.h>


#define CHILD(node) ((node) * 2 + 1)


static void heapify( int a[], int i, int n )
{
  /* Heapify an unknown number of subtrees */
  while ( CHILD( i ) < n ) {
    int child = CHILD( i );

    /* Pick the smaller of the two children */
    if ( child + 1 < n && a[child] > a[child + 1] )
      ++child;

    /* Move the smallest node to the root */
    if ( a[i] > a[child] ) {
      int temp = a[i];
      a[i] = a[child];
      a[child] = temp;
    }

    /* Move to the next node */
    ++i;
  }
}


void make_heap( int a[], int n )
{
  int i = n / 2;

  while ( i-- > 0 )
    heapify( a, i, n );
}


void pop_heap( int heap[], int n )
{
  int temp = heap[0];
  heap[0] = heap[n];
  heap[n] = temp;
  heapify( heap, 0, n );
}


int main( void )
{
  int heap[10];
  int i;
  int n;

  for ( i = 0; i < 10; i++ )
    heap[i] = rand() % 100;

  /* Build a min heap */
  make_heap( heap, 10 );

  /* Prove that it's a min heap */
  for ( n = 10; n >= 0; n-- ) {
    printf( "%d ", heap[0] );
    pop_heap( heap, n );
  }

  putchar( '\n' );

  return 0;
}
commented: Are you always this helpful and descriptive? :D - ~s.o.s~ +12
Member Avatar for srujana.k

is there any difference between the construction of max heap and min heap??

Member Avatar for Narue

>is there any difference between the construction of max heap and min heap??
The only difference is the ordering of your data. In a min heap, the smallest elements have priority, and in a max heap the largest elements have priority.

Member Avatar for sandy423

can you please explain with example

Member Avatar for Narue

>can you please explain with example
What's wrong with the examples that were already given in this thread?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.