## Featured Replies in this Discussion

0

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

2

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

You

This article has been dead for over six months: Start a new discussion instead