A Data Structure Heap
• A heap is a nearly complete binary tree which
can be easily implemented on an array.
1
6
2 3
5 3 6 5 3 2 4 1
4 5 6
2 4 1
Nearly complete binary tree
• Every level except bottom is complete.
• On the bottom, nodes are placed as left as possible.
1 1
6 6
2 2 3
3 5 3
5 3
4 5 6 4 5 6
2 2 4 1
1 4
No! Yes!
Heap
• Definition: A heap can be defined as a binary tree
with keys assigned to its nodes, one key per
node, provided the following two conditions are
met:
– The shape property —the binary tree is
essentially complete (or simply complete), i.e., all
its levels are full except possibly the last level,
where only some rightmost leaves may be
missing.
– The parental dominance or heap property —the
key in each node is greater than or equal to the
Hea Hea
p? p?
Hea
p?
Properties of Heap
1. There exists exactly one essentially complete
binary tree with n nodes. Its height is equal to
2. The root of a heap always contains its
largest element.
3. A node of a heap considered with all its
descendants is also a heap.
Properties of Heap
4. A heap can be implemented as an array by
recording its elements in the top down,
left-to-right fashion.
1 1
6 6
2 2 3
3 5 3
5 3
4 5 6 4 5 6
2 2 4 1
1 4
No! Yes!
Construction of Heap
• There are two principal alternatives for
constructing Heap.
1. Bottom-up heap construction
2. Top-down heap construction
Example from textbook
Building a Max-Heap
e.g., 4, 1, 3, 2, 16, 9, 10, 14, 8, 7.
Building a Max-Heap 4, 1, 3, 2, 16, 9, 10, 14, 8, 7.
1 3
1 1
2 9
6 0
14 8 7
1
6
1 1
4 0
7 9 3
8
2 4 1
• Sort the given list of numbers using heap sort:
2, 9, 7, 6, 5, 8. (08 Marks)
Illustration -2
Inserting a new key (10)
Illustration
Delete an item from a heap
Delete an item from a
heap
Maximum Key Deletion from a heap
1. Exchange the root’s key with the last key K of the heap.
2. Decrease the heap’s size by 1.
3. “Heapify” the smaller tree by sifting K down the tree exactly in the
same way we did it in the bottom-up heap construction algorithm.
That is, verify the parental dominance for K: if it holds,
we are done;
if not, swap K with the larger of its children and repeat this
operation until the parental dominance condition holds for K in its
new position.
The efficiency of deletion is O (log n)
Heap Sort
• This is a two-stage algorithm that works as
follows.
Stage 1 (heap construction): Construct a heap
for a given array.
Stage 2 (maximum deletions): Apply the
root-deletion
operation n−1 times to the remaining heap.
• As a result, the array elements are
eliminated in decreasing order.
• Since under the array implementation of heaps
an element being deleted is placed last, the
resulting array will be exactly the original array
sorted in increasing order.
Heap sort - Illustration
2, 5, 6, 7, 8, 9
Heapsort - Analysis of
efficiency
• Stage-1: heap construction - O(n)
• Stage-2: For the number of key comparisons,
C(n), needed for eliminating the root keys from
the heaps of diminishing sizes from n to 2, we
get the following inequality:
C(n) ∈ O(n log n)
• For both stages, we get O(n) + O(n log n) =
O(n log n).
Analysis
• A more detailed analysis shows that the time
efficiency of heapsort is, in fact, in Θ(n log n)
in both the worst and average cases.
• Thus, heapsort’s time efficiency falls in
the same class as that of mergesort.
• heapsort is in-place, i.e., it does not require
any extra storage.
• Timing experiments on random files show that
heapsort runs more slowly than quicksort but
can be competitive with mergesort.
COMPARISION COUNTING SORT
Distribution counting
HORSPOOL ALGORTHIM
• Examples refer classnotes and textbook
