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
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:
Item
Item
Item
... 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
... 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
... 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:
Item
Item
Item
Insertion with Heaps | 11/16 |
Insertion is a two-step process
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:
... 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