difference between min heap and max heap...

[cezarjont]

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

[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;
}

[cezarjont]

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

[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;
}

[srujana.k]

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

[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.

[sandy423]

can you please explain with example

[Narue]

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