Binary Heap is a #Priority Queue/Heap that use #Binary Search Tree as its chassis. It can be represented in the form of simple array.
Characteristics
- It should always be a complete binary tree
- Having a height of \(\lfloor \log N \rfloor\)
- Every node, except root, will have a larger key than its parent
Analysis
- Insert will result in \(O(1)\) on average and \(O(\log N)\) at worst case
- DeleteMin will result in \(O(\log N)\)
- FindMin will result in \(O(1)\)
Additional Operations
- DecreaseKey(P, N, H): percolate up
- IncreaseKey(P, N, H): percolate down
- Delete(P, H)
- BuildHeap(H)
Implementation
#ifndef _BinHeap_H
struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;
PriorityQueue Initialise(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
struct HeapStruct {
int Capacity;
int Size;
ElementType *Elements;
};
PriorityQueue Initialise(int MaxElements) {
PriorityQueue H;
if (MaxElements < MinPQSize)
Error("Priority queue size is too small");
H = malloc(sizeof(struct HeapStruct));
if (H == NULL)
FatalError("Out of Space!!!");
// Allocate the array plus one extra for sentinel
H->Elements = malloc((MaxElements + 1) * sizeof(ElementType));
if (H->Elements == NULL)
FatalError("Out of Space!!!");
H->Capacity = MaxElements;
H->Size = 0;
H->Elements[0] = MinData;
}
void Insert(ElementType X, PriorityQueue H) {
int i;
if (IsFull(H)) {
Error("Priority queue is full");
return;
}
// Percolate up
for (i = ++H->Size; H->Elements[i/2] > X; i /= 2)
H->Elements[i] = H->Elements[i/2];
H->Elements[i] = X;
}
ElementType DeleteMin(PriorityQueue H) {
int i, Child;
ElementType MinElement, LastElement;
if (IsEmpty(H)) {
Error("Priority queue is empty");
return H->Elements[0];
}
MinElement = H->Elements[1];
LastElement = H->Elements[H->Size--];
for (i = 1; i*2 <= H->Size; i = Child) {
// Find smaller child
Child = i * 2;
if (Child != H->Size && H->Elements[Child + 1] < H->Elements[Child])
Child++;
// Percolate down one level
if (LastElement > H->Elements[Child])
H->Elements[i] = H->Elements[Chlid];
else
break;
}
H->Elements[i] = LastElement;
return MinElement;
}