Page 260 - DCAP407_DATA_STRUCTURE

Unit 14: Heaps

fori ←n/2 down to 1 do
k←i; v←H[k]
heap←false
while not heap and 2 * k ≤ n do

j←2 * k
if j <n //there are two children
if H[ j ]<H[ j + 1] j ←j + 1
if v ≥ H[j ]
heap←true
else H[k]←H[j ]; k←j
H[k]←v
Let us now trace the bottom-up heap construction algorithm.

Algorithm Tracing of Bottom-up Heap Construction
n=5
Algorithm: Heap bottom-up (H [1...5])
//Constructs a heap from the elements of a given array
// by the bottom-up algorithm

//Input: An array H[1..5] of orderable items
//Output: A heap H[1..5]
for i ←5/2=1 down to 1 do
k←1; v←H[1]
heap←false
while not heap and 2 * 1 ≤ 5 do
j ←2 * 1

if j <5 //there are five children
if H[ 2 ]<H[ 2 + 1] 2 ←2 + 1
if v ≥ H[2 ]
heap←true
else H[1]←H[2 ]; 1←2
H[1]←v

Construct a heap for the list 2, 9, 7, 6, 2, 8, 5 using the bottom-up construction algorithm.

Top-down Heap Construction Algorithm
The top-down heap construction algorithm is less efficient and it constructs a heap by successive
insertions of a new key into a previously constructed heap. The insertion of a new key into a heap is
discussed in the section 14.2.

LOVELY PROFESSIONAL UNIVERSITY 253