Given an integer array, heapify it into a min-heap array. If there are multiple solutions, return any one.
For a heap array
A is the root of heap, and for each
A[i * 2 + 1] is the left child of
A[i * 2 + 2] is the right child of
What is heap?
Heap is a data structure, which usually have three methods: push, pop and top. where “push” add a new element the heap, “pop” delete the minimum/maximum element in the heap, “top” return the minimum/maximum element.
What is heapify?
Convert an unordered integer array into a heap array. If it is min-heap, for each element
A[i], we will get
A[i * 2 + 1] >= A[i] and
A[i * 2 + 2] >= A[i].
[1,2,3,4,5] or any legal heap array.
The following algorithm uses sorting, which has the time complexity of O(nlogn).