Lecture Notes for CS 512, Algorithm Design
Binary Heaps - 16 February 2000
- 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
- the root of the tree obeying the heap property
- a heap is a linerization of a binary tree in an array
- the parent
h[i] has left child h[2i] and right child h[2i
+ 1]
- node
h[i], i > 1, has parent h[floor(i/2)]
- the binary tree represented by a heap is an almost-complete binary tree
- a heap implements a priority queue with operations insert() and
remove-max()
- heapify(
h, i) makes h[i] be a heap assuming h[left(i)] and
h[right(i)] are heaps
- 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)
- creating a heap from an unsorted array
- the lower half is already a bunch of one-element heaps
- work from the bottom of the upper half to the top, calling heapify()
at each element
- 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.