Sorting Heaps

Computer Science Level 3

1	`A = { 6 , 2 , 1 , 0 }`

Consider the max heap above. After the end of the first iteration of the loop that takes place in executing Heap Sort , the array for of the max heap will take the form of :

1	`A = {a , b , c , d }`

Where $a$ , $b$ , $c$ and $d$ are positive integers. Input $1000a+100b+10c+d$ as the answer.

The answer is 2016.

1 solution

Hasmik Garyaka
Oct 14, 2017

First we swap first and last elements. A={0,2,1,6}. Then execute heapify procedure for first 3 elements. And get {2,0,1,6} ```Pascal Heapify(A, i)

left ← 2i

right ← 2i+1

largest ← i

if left ≤ A.heap_size и A[left] > A[largest]

then largest ← left

if right ≤ A.heap_size и A[right] > A[largest]

then largest ← right

if largest ≠ i then swap A[i] ↔ A[largest] Heapify(A, largest) ```

Sorting Heaps

The answer is 2016.

1 solution

0 pending reports