Building a Heap solved by 874

Problem

A binary heap is a binary tree based data structure that is often used to implement priority queues. Binary heaps, in turn, can be easily implemented using an array if the underlying tree is a complete binary tree. The tree nodes have a natural ordering: row by row, starting at the root and moving left to right within each row. If there are $n$ nodes, this ordering specifies their positions $1, 2, \dots,n$ within the array. Moving up and down the tree is easily simulated on the array, using the fact that node number $j$ has parent $\lceil j/2 \rceil$ and children $2j$ and $2j + 1$.

The goal of this problem is to build a heap from the given array. For this, go from the end to the beginning of a given array and let each element "bubble up".

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Given: A positive integer $n \le 10^5$ and array $A[1..n]$ of integers from $-10^5$ to $10^5$.

Return: A permuted array $A$ satisfying the binary max heap property: for any $2 \le i \le n$, $A[\lfloor i/2 \rfloor] \ge A[i]$.

Sample Dataset

5
1 3 5 7 2

Sample Output

7 5 1 3 2

Running time

Since each "bubble up" operation requires only $O(\log n)$ time the running time of this algorithm is $O(n \log n)$. A more careful analysis shows that the running time is in fact just linear.