Feb. 21, 2014, 4:23 p.m. by Rosalind Team

**Topics**:
Sorting

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

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

Return: A permuted array

5 1 3 5 7 2

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.