Convert array into heap
Problem Introduction
In this problem you will convert an array of integers into a heap. This is the crucial step of the sorting
algorithm called HeapSort. It has guaranteed worst-case running time of 𝑂(𝑛 log 𝑛) as opposed to QuickSort’s
average running time of 𝑂(𝑛 log 𝑛). QuickSort is usually used in practice, because typically it is faster, but
HeapSort is used for external sort when you need to sort huge files that don’t fit into memory of your
computer.
Problem Description
Task. The first step of the HeapSort algorithm is to create a heap from the array you want to sort. By the
way, did you know that algorithms based on Heaps are widely used for external sort, when you need
to sort huge files that don’t fit into memory of a computer?
Your task is to implement this first step and convert a given array of integers into a heap. You will
do that by applying a certain number of swaps to the array. Swap is an operation which exchanges
elements 𝑎𝑖 and 𝑎𝑗 of the array 𝑎 for some 𝑖 and 𝑗. You will need to convert the array into a heap using
only 𝑂(𝑛) swaps, as was described in the lectures. Note that you will need to use a min-heap instead
of a max-heap in this problem.
Input Format. The first line of the input contains single integer 𝑛. The next line contains 𝑛 space-separated
integers 𝑎𝑖
.
Constraints. 1 ≤ 𝑛 ≤ 100 000; 0 ≤ 𝑖, 𝑗 ≤ 𝑛 − 1; 0 ≤ 𝑎0, 𝑎1, . . . , 𝑎𝑛−1 ≤ 109
. All 𝑎𝑖 are distinct.
Output Format. The first line of the output should contain single integer 𝑚 — the total number of swaps.
𝑚 must satisfy conditions 0 ≤ 𝑚 ≤ 4𝑛. The next 𝑚 lines should contain the swap operations used
to convert the array 𝑎 into a heap. Each swap is described by a pair of integers 𝑖, 𝑗 — the 0-based
indices of the elements to be swapped. After applying all the swaps in the specified order the array
must become a heap, that is, for each 𝑖 where 0 ≤ 𝑖 ≤ 𝑛 − 1 the following conditions must be true:
1. If 2𝑖 + 1 ≤ 𝑛 − 1, then 𝑎𝑖 < 𝑎2𝑖+1.
2. If 2𝑖 + 2 ≤ 𝑛 − 1, then 𝑎𝑖 < 𝑎2𝑖+2.
Note that all the elements of the input array are distinct. Note that any sequence of swaps that has
length at most 4𝑛 and after which your initial array becomes a correct heap will be graded as correct.
Time Limits. C: 1 sec, C++: 1 sec, Java: 3 sec, Python: 3 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3
sec, Ruby: 3 sec, Scala: 3 sec.
Memory Limit. 512MB.
Sample 1.
Input:
5
5 4 3 2 1
Output:
3
1 4
0 1
1 3
After swapping elements 4 in position 1 and 1 in position 4 the array becomes 5 1 3 2 4.
2
After swapping elements 5 in position 0 and 1 in position 1 the array becomes 1 5 3 2 4.
After swapping elements 5 in position 1 and 2 in position 3 the array becomes 1 2 3 5 4, which is
already a heap, because 𝑎0 = 1 < 2 = 𝑎1, 𝑎0 = 1 < 3 = 𝑎2, 𝑎1 = 2 < 5 = 𝑎3, 𝑎1 = 2 < 4 = 𝑎4.
Sample 2.
Input:
5
1 2 3 4 5
Output:
0
The input array is already a heap, because it is sorted in increasing order.
Starter Files
There are starter solutions only for C++, Java and Python3, and if you use other languages, you need
to implement solution from scratch. Starter solutions read the array from the input, use a quadratic time
algorithm to convert it to a heap and use Θ(𝑛
2
) swaps to do that, then write the output. You need to replace
the Θ(𝑛
2
) implementation with an 𝑂(𝑛) implementation using no more than 4𝑛 swaps to convert the array
into heap.
What to Do
Change the BuildHeap algorithm from the lecture to account for min-heap instead of max-heap and for
0-based indexing.
# Solution in python3
class HeapBuilder:
"""Converts an array of integers into a min-heap.
A binary heap is a complete binary tree which satisfies the heap ordering
property: the value of each node is greater than or equal to the value of
its parent, with the minimum-value element at the root.
Samples:
>>> heap = HeapBuilder()
>>> heap.array = [5, 4, 3, 2, 1]
>>> heap.generate_swaps()
>>> heap.swaps
[(1, 4), (0, 1), (1, 3)]
>>> # Explanation: After swapping elements 4 in position 1 and 1 in position
>>> # 4 the array becomes 5 1 3 2 4. After swapping elements 5 in position 0
>>> # and 1 in position 1 the array becomes 1 5 3 2 4. After swapping
>>> # elements 5 in position 1 and 2 in position 3 the array becomes
>>> # 1 2 3 5 4, which is already a heap, because a[0] = 1 < 2 = a[1],
>>> # a[0] = 1 < 3 = a[2], a[1] = 2 < 5 = a[3], a[1] = 2 < 4 = a[4].
>>> heap = HeapBuilder()
>>> heap.array = [1, 2, 3, 4, 5]
>>> heap.generate_swaps()
>>> heap.swaps
[]
>>> # Explanation: The input array is already a heap, because it is sorted
>>> # in increasing order.
"""
def __init__(self):
self.swaps = []
self.array = []
@property
def size(self):
return len(self.array)
def read_data(self):
"""Reads data from standard input."""
n = int(input())
self.array = [int(s) for s in input().split()]
assert n == self.size
def write_response(self):
"""Writes the response to standard output."""
print(len(self.swaps))
for swap in self.swaps:
print(swap[0], swap[1])
def l_child_index(self, index):
"""Returns the index of left child.
If there's no left child, returns -1.
"""
l_child_index = 2 * index + 1
if l_child_index >= self.size:
return -1
return l_child_index
def r_child_index(self, index):
"""Returns the index of right child.
If there's no right child, returns -1.
"""
r_child_index = 2 * index + 2
if r_child_index >= self.size:
return -1
return r_child_index
def sift_down(self, i):
"""Sifts i-th node down until both of its children have bigger value.
At each step of swapping, indices of swapped nodes are appended
to HeapBuilder.swaps attribute.
"""
min_index = i
l = self.l_child_index(i)
r = self.r_child_index(i)
if l != -1 and self.array[l] < self.array[min_index]:
min_index = l
if r != - 1 and self.array[r] < self.array[min_index]:
min_index = r
if i != min_index:
self.swaps.append((i, min_index))
self.array[i], self.array[min_index] = \
self.array[min_index], self.array[i]
self.sift_down(min_index)
def generate_swaps(self):
"""Heapify procedure.
It calls sift down procedure 'size // 2' times. It's enough to make
the heap completed.
"""
for i in range(self.size // 2, -1, -1):
self.sift_down(i)
def solve(self):
self.read_data()
self.generate_swaps()
self.write_response()
if __name__ == "__main__":
heap_builder = HeapBuilder()
heap_builder.solve()