C Binary Heap

A binary heap is a heap a data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:

• The shape property: the tree is an almost complete binary tree; that is, all levels of the tree, except possibly the last one (deepest), are filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
• The heap property: each node is greater than or equal to each of its children according to some comparison predicate fixed to the entire data structure.

“Greater than” means according to whatever comparison function is chosen to sort the heap, not necessarily “greater than” in the mathematical sense (since the quantities are not always numerical). Heaps where the comparison function is mathematical “greater than” are called max-heaps; those where the comparison function is mathematical “less than” are called “min-heaps.” Conventionally, min-heaps are used since they are readily applicable for use in priority queues.

Note that the heap property does not specify the ordering of siblings in a heap, so the two children of a parent can be freely interchanged, as long as this does not violate the shape and heap properties (compare with treap).

The binary heap is a special case of the d-ary heap in which d = 2.

It is possible to modify the heap structure to allow extraction of both the smallest and largest element in O(logn) time. To do this the rows alternate between min heap and max heap. The algorithms are roughly the same, but in each step must consider the alternating rows with alternating comparisons. The performance is roughly the same as a normal single direction heap. This idea can be generalized to a min-max-median heap.

typedef int ElementType;

#ifndef _BinHeap_H
#define _BinHeap_H

struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

PriorityQueue Initialize(int MaxElements);
void Destroy(PriorityQueue H);
void MakeEmpty(PriorityQueue H);
void Insert(ElementType X, PriorityQueue H);
ElementType DeleteMin(PriorityQueue H);
ElementType FindMin(PriorityQueue H);
int IsEmpty(PriorityQueue H);
int IsFull(PriorityQueue H);

#endif
Code language: C++ (cpp)

#include "binheap.h"
#include "fatal.h"
#include <stdio.h>

#define MinPQSize (10)
#define MinData (-32767)

struct HeapStruct {
    int Capacity;
    int Size;
    ElementType *Elements;
};

PriorityQueue Initialize(int MaxElements) {
    PriorityQueue H;

    /* 1*/ if (MaxElements < MinPQSize)         /* 2*/ Error("Priority queue size is too small");     /* 3*/ H = malloc(sizeof ( struct HeapStruct));     /* 4*/ if (H == NULL)         /* 5*/ FatalError("Out of space!!!");     /* Allocate the array plus one extra for sentinel */     /* 6*/ H->Elements = malloc((MaxElements + 1)
            * sizeof ( ElementType));
    /* 7*/ if (H->Elements == NULL)
        /* 8*/ FatalError("Out of space!!!");

    /* 9*/ H->Capacity = MaxElements;
    /*10*/ H->Size = 0;
    /*11*/ H->Elements[ 0 ] = MinData;

    /*12*/ return H;
}

/* END */

void MakeEmpty(PriorityQueue H) {
    H->Size = 0;
}

/* H->Element[ 0 ] is a sentinel */

void Insert(ElementType X, PriorityQueue H) {
    int i;

    if (IsFull(H)) {
        Error("Priority queue is full");
        return;
    }

    for (i = ++H->Size; H->Elements[ i / 2 ] > X; i /= 2)
        H->Elements[ i ] = H->Elements[ i / 2 ];
    H->Elements[ i ] = X;
}

/* END */

ElementType DeleteMin(PriorityQueue H) {
    int i, Child;
    ElementType MinElement, LastElement;

    /* 1*/ if (IsEmpty(H)) {
        /* 2*/ Error("Priority queue is empty");
        /* 3*/ return H->Elements[ 0 ];
    }
    /* 4*/ MinElement = H->Elements[ 1 ];
    /* 5*/ LastElement = H->Elements[ H->Size-- ];

    /* 6*/ for (i = 1; i * 2 <= H->Size; i = Child) {
        /* Find smaller child */
        /* 7*/ Child = i * 2;
        /* 8*/ if (Child != H->Size && H->Elements[ Child + 1 ]
                /* 9*/ < H->Elements[ Child ])
            /*10*/ Child++;

        /* Percolate one level */
        /*11*/ if (LastElement > H->Elements[ Child ])
            /*12*/ H->Elements[ i ] = H->Elements[ Child ];
        else
            /*13*/ break;
    }
    /*14*/ H->Elements[ i ] = LastElement;
    /*15*/ return MinElement;
}

ElementType FindMin(PriorityQueue H) {
    if (!IsEmpty(H))
        return H->Elements[ 1 ];
    Error("Priority Queue is Empty");
    return H->Elements[ 0 ];
}

int IsEmpty(PriorityQueue H) {
    return H->Size == 0;
}

int IsFull(PriorityQueue H) {
    return H->Size == H->Capacity;
}

void Destroy(PriorityQueue H) {
    free(H->Elements);
    free(H);
}

#if 0

for (i = N / 2; i > 0; i--)
    PercolateDown(i);

#endif
Code language: C++ (cpp)

#include "binheap.h"
#include 

#define MaxSize (1000)

main() {
    PriorityQueue H;
    int i, j;

    H = Initialize(MaxSize);
    for (i = 0, j = MaxSize / 2; i < MaxSize; i++, j = (j + 71) % MaxSize)
        Insert(j, H);

    j = 0;
    while (!IsEmpty(H))
        if (DeleteMin(H) != j++)
            printf("Error in DeleteMin, %d\n", j);
    printf("Done...\n");
    return 0;
}
Code language: C++ (cpp)