Binary Heap

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

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;
}
Links to this page
#data-structure #heap #tree