Lecture Notes for CS 512, Algorithm Design

Binary Heaps - 16 February 2000

1. the heap property for n-ary trees: the value stored at v is at least as large as the value stored at any of v's children

2. the root of the tree obeying the heap property

3. a heap is a linerization of a binary tree in an array

   1. the parent h[i] has left child h[2i] and right child h[2i + 1]

   2. node h[i], i > 1, has parent h[floor(i/2)]

4. the binary tree represented by a heap is an almost-complete binary tree

5. a heap implements a priority queue with operations insert() and remove-max()

6. heapify(h, i) makes h[i] be a heap assuming h[left(i)] and h[right(i)] are heaps

   1. remove-max() is implemented by extracting h[1] from the heap, replacing it with the last node in the heap, and calling heapify(h, 1)

7. creating a heap from an unsorted array

   1. the lower half is already a bunch of one-element heaps

   2. work from the bottom of the upper half to the top, calling heapify() at each element

8. to insert into a heap, move smaller parents into the hole and add the new value as the child of the first larger parents

This page last modified on 28 February 2000.