CSC 378: Data Structures and Algorithm Analysis

ARRAY HEAPS

[CLR 7.1 - 7.4]

There are many implementations of the priority queue ADT; the heap is only one of these implementations. Other implementations (some of which will be discussed later) include leftist trees, binomial heaps, and Fibonacci heaps.

Here, we'll discuss "heaps". Sometimes these will be called "array heaps" to distinguish them from the other implementations.

Structure of a Heap

Take a binary tree

with the properties

Every level but the last is full.
The bottom level is filled from the left up to some point.
key( i ) <= key( parent( i ) ) for every node i but the root.

and implement this in an array

where each element in A contains one node of the tree.

Let denote the node of the tree that is stored in A[ i ]. Then

The root is 1.
The parent of i is , and is written P( i ).
The left child of i is , written L( i ).
The right child of i is , written R( i ).
The key of i is written key( i ).
The data of i is written data( i ).

Each array element stores one datum, so element A[ i ] stores data( i ). But within A[ i ], there's a field called the key. In C notation, the field might be accessed with A[ i ].key.

This array structure, along with its properties, is called a heap.

The Heapify procedure

[CLR 7.2]

Here we'll describe a procedure which is used in many heap operations. The procedure is called Heapify. It reorganizes a subtree of a heap in order to satisfy the three heap properties.

Here's an example:

The subtrees rooted at L( i ) and R( i ) are heaps.
But the tree rooted at i is not a heap.

A call to Heapify( A, i ) will it a heap.

Here's the Heapify procedure [CLR pg 143]:

Quick Analysis of Heapify

Define height( i ) to be the maximum number of edges from i down to a leaf. If i is a leaf, height( i ) is 0.

Then the running time is proportional to the height, because

Since the heap forms a complete binary tree of nodes, its height is in . Therefore,

Example of Heapify

Step 1: Heapify(A,1)
Step 2: Heapify(A,2)
Step 3: Heapify(A,5)

Clarification

There is no relation between the elements in different subtrees:

The only ordering is along a root-to-leaf path:

In particular, each level is not necessarily ordered!

Other Heap Operations

Maximum

Extract Maximum

Idea: Move the bottom-right element to the root and heapify.

Insert

Idea: Percolate x up past all black nodes, if the heap property is violated.

This kind of heap can support either min and extract-min or max and extract-max, but not both! To support min and extract-min, the comparisons have to be reversed in all the code above.