BINARY HEAP
Dr. Megha Ummat
Heaps
◦ The Binary Heap data structure is an array
object that we can view as a nearly
complete binary tree, as shown in Figure.
◦ Each node of the tree corresponds to an
element of the array.
◦ The tree is completely filled on all levels
except possibly the lowest, which is filled
from the left up to a point.
Heaps
◦ An array A[1:n] that represents a heap is an object
with an attribute A: heap-size, which represents how
many elements in the heap are stored within array A.
◦ Although A[1:n] may contain numbers, only the
elements in A[1:heapsize], where 0 ≤ A.heapsize ≤ n,
are valid elements of the heap.
◦ The root of the tree is A[1], and given the index i of a
node, we can easily compute the parent, left child and
right child
Types of Heap
◦ There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the
values in the nodes satisfy a heap property.
◦ In a max-heap, the max-heap property is that for every node i, other than the root,
◦ Thus, the largest element in a max-heap is stored at the root, and the subtree rooted at
a node contains values no larger than that contained at the node itself.
◦ The min-heap property is that for every node i other than the root,
◦ The smallest element in a min-heap is at the root.
Types of Heaps
◦ The heapsort algorithm uses max-heaps. Min-heaps commonly
implement priority queues.
◦ Since a heap of n elements is based on a complete binary tree, its height
is O(lg n). The basic operations on heaps run in time at most proportional
to the height of the tree and thus take O(lg n) time.
Maintaining the Heap Property
◦ The procedure MAX-HEAPIFY takes its inputs an array A with the heap-size
attribute and an index i into the array.
◦ When it is called, MAX-HEAPIFY assumes that the binary trees rooted at
LEFT (i) and RIGHT(i) are max-heaps, but that A[i] might be smaller than its
children, thus violating the max-heap property.
◦ MAX-HEAPIFY lets the value at A[i] float down in the max-heap so that the
subtree rooted at index i obeys the maxheap property.
◦ Figure 6.2 illustrates
Maintaining the Heap Property
Maintaining the Heap Property
◦ Each step determines the largest of the elements A[i], A[LEFT(i)], and A[RIGHT(i)]
and stores the index of the largest element in largest .
◦ If A[i] is largest, then the subtree rooted at node i is already a max-heap and nothing
else needs to be done. Otherwise, one of the two children contains the largest element.
◦ Positions i and largest swap their contents, which causes node i and its children to
satisfy the max-heap property.
◦ The node indexed by largest, however, just had its value decreased, and thus the
subtree rooted at largest might violate the max-heap property.
◦ Consequently, MAX-HEAPIFY calls itself recursively on that subtree.
Maintaining the Heap Property
◦ The action of MAX-HEAPIFY
(A, 2), where A.heap-size =10.
◦ The node that potentially
violates the max-heap property
is shown in blue.
◦ Two recursive calls
◦ MAX-HEAPIFY (A,2)
◦ MAX-HEAPIFY (A,9)
Maintaining the Heap Property
◦ Let T(n) be the worst case running time that the procedure takes on a subtree of
size at most n.
◦ For a tree rooted at a given node i, the running time is the Θ (1) time to fix up
the relationships between A[i], A[LEFT(i)] and A[RIGHT(i)], plus the time to
run MAX-HEAPIFY on a subtree rooted at one of the children of node i.
◦ Symbolized by the recurrence:
◦ Case 2 of master theorem, T(n) = O(lg n)
Building a Heap
◦ The procedure BUILD-MAX-HEAP converts an array A[1:n] into a max-heap
by calling MAX-HEAPIFY in a bottom-up manner.
◦ Elements in the subarray are all leaves of the tree, and so
each is a 1-element heap to begin with. BUILD-MAX-HEAP goes through the
remaining nodes of the tree and runs MAX-HEAPIFY on each one.
Building a Heap
Building a Heap
Building a Heap
Building a Heap
◦ We can compute a simple upper bound on the running time of BUILD-MAX-
HEAP as follows.
◦ Each call to MAX-HEAPIFY costs O(lg n) time, and BUILD-MAX-HEAP
makes O(n) such calls.
◦ Thus, the running time is O(n lg n)
