Week 11: Heaps

Heaps

Heaps

2/16

Heaps can be viewed as trees with top-to-bottom ordering
(cf. binary search trees which have left-to-right ordering)

... Heaps

3/16

Heaps are typically used for implementing Priority Queues

• priorities determined by order on keys
• new items added initially at lower-most, right-most leaf
• then new item "drifts up" to appropriate level in tree
• items are always deleted by removing root (top priority)

Insertion cost = O(logN),   Deletion cost = O(logN)

... Heaps

4/16

Heaps grow as follows (level-order):

... Heaps

5/16

BSTs are typically implemented as linked data structures.

Heaps are typically implemented via arrays.

Simple index calculations allow navigation through the tree:

• left child of Item at index i is located at 2i
• right child of Item at index i is located at 2i+1
• parent of Item at index i is located at i/2

... Heaps

6/16

Heap data structure:

typedef struct HeapRep {
   Item *items;  // array of Items
   int  nitems;  // #items in array
   int  nslots;  // #elements in array
} HeapRep;

typedef HeapRep *Heap;

Initialisation is similar to that for simple Hash Tables.

One difference: we use indexes from 1..nitems

Note: unlike "normal" C arrays, nitems also gives index of last item

... Heaps

7/16

Creating new heap:

Heap newHeap(int N)
{
   Heap new = malloc(sizeof(HeapRep));
   Item *a = malloc((N+1)*sizeof(Item));
   assert(new != NULL && a != NULL);
   new->items = a;   // no initialisation needed
   new->nitems = 0;  // counter and index
   new->nslots = N;  // index range 1..N
}

Insertion with Heaps

8/16

Insertion is a two-step process

• add new element at next available position on bottom row
  (but this might violate heap property; new value larger than parent)
• reorganise values along path to root to restore heap

... Insertion with Heaps

9/16

Insertion into heap:

void insert(Heap h, Item it)
{
   assert(h->nitems < h->nslots);
   h->nitems++;
   h->items[h->nitems] = it;
   fixUp(h->items, h->nitems);
}

Always start new item at next available position on bottom level
(corresponds to next free element in the array (i.e. items[nitems])

Heaps

10/16

Heaps can be viewed as trees with top-to-bottom ordering.

Heaps are typically implemented via arrays.

Simple index calculations allow navigation through the tree:

• left child of Item at index i is located at 2i
• right child of Item at index i is located at 2i+1
• parent of Item at index i is located at i/2

Insertion with Heaps

11/16

Insertion is a two-step process

• add new element at bottom-most, rightmost position
  (but this might violate heap property; new value larger than parent)
• reorganise values along path to root to restore heap

void insert(Heap h, Item it)
{
   assert(h->nitems < h->nslots);
   h->nitems++;
   h->items[h->nitems] = it;
   fixUp(h->items, h->nitems);
}

... Insertion with Heaps

12/16

Bottom-up heapify:

// force value at a[i] into correct position
void fixUp(Item a[], int i)
{
   while (i > 1 && less(a[i/2],a[i])) {
      swap(a, i, i/2);
      i = i/2;  // integer division
   }
}
void swap(Item a[], int i, int j)
{
   Item tmp = a[i];
   a[i] = a[j];
   a[j] = tmp;
}

Exercise: Heap Construction

13/16

Show the construction of the heap produced by inserting:

Deletion with Heaps

14/16

Deletion is a three-step process:

• replace root value by bottom-most, rightmost value
• remove bottom-most, rightmost value
• reorganise values along path from root to restore heap

... Deletion with Heaps

15/16

Deletion from heap (always remove root):

Item delete(Heap h)
{
   Item top = h->items[1];
   // overwrite first by last
   h->items[1] = h->items[h->nitems];
   h->nitems--;
   // move new root to correct position
   fixDown(h->items, 1, h->nitems);
   return top;
}

... Deletion with Heaps

16/16

Top-down heapify:

// force value at a[i] into correct position
// note that N gives max index *and* # items
void fixDown(Item a[], int i, int N)
{
   while (2*i <= N) {
      // compute address of left child
      int j = 2*i;
      // choose larger of two children
      if (j < N && less(a[j], a[j+1])) j++;
      if (!less(a[i], a[j])) break;
      swap(a, i, j);
      // move one level down the heap
      i = j;
   }
}

Produced: 11 Oct 2017