Heapify
Description
Given an integer array, heapify it into a min-heap array.
For a heap array A, A[0] is the root of heap, and for each A[i],
A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].
Clarification
- 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].
- What if there is a lot of solutions?
- Return any of them.
Example
Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.
Challenge
O(n) time complexity
解题方法
构造堆的基本操作有两种：siftdown和siftup。两种操作在本质上是相同的，处理不符合堆定义的结点直至满足规则。以构造最小堆为例：
siftup：当前结点比父结点大，两者交换，迭代操作直至当前结点小于其父结点。siftdown：当前结点比子结点大，同较小的儿子结点交换，迭代操作直至当前结点小于两个儿子结点。
对一个结点进行siftup或siftdown时涉及的实际操作数，与该结点需要移动的距离正相关。
- 对
siftup是结点从树底层开始向上移动的距离，所以构造完成时树顶端结点的移动代价较高，自底向上siftup构造堆时，大量的叶子结点需要移动约为logn的距离。 - 对
siftdown是结点从树顶端开始向下移动的距离，所以构造完成时叶子节点的移动代价较高，自顶向下siftdown构造堆时，只有根结点等少数几个结点需要移动约为logn的长距离。 - 不难发现，两种方式构造堆所需要的操作数是不同的。
假设树的高度为h = logn，那么在最坏情况下，自顶向下siftdown构造堆所需要的操作数为：
sum1 = (0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1)
使用泰勒级数对其进行近似可以得到时间复杂度最坏为O(n)。具体证明过程请参考链接。
同样假设在最坏情况下，自底向上siftup构造堆所需要的操作数为：
sum2 = (h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1)
siftup所需要的操作更多，其中第一项h * n/2 = 1/2 * nlogn，因此其时间复杂度最差为O(nlogn)。
以上内容其实会引出一个问题：
如果构造堆的时间复杂度为
O(n)，那么堆排序的时间复杂度为什么是O(nlogn)呢？
具体分析可参考本文提供的参考链接。
易错点
- 在对数组遍历处理时，注意
i的取值范围和取值顺序，尤其是siftdown实现。- 在
siftup和siftdown函数中，循环终止的条件有两个，一个是自变量k的取值范围，另一个是满足最小堆的特性。
一、自底向上siftup
根据最小堆的定义，对数组中的每个元素，依次进行siftup操作。
siftup：当前结点比父结点小，两者交换，迭代操作直至当前结点大于其父结点。
Java 实现
public
class
Solution
{
/**
*
@param
A: Given an integer array
*
@return
: void
*/
public
void
heapify
(
int
[] A)
{
if
(A ==
null
|| A.length ==
0
) {
return
;
}
for
(
int
i =
0
; i
<
A.length; i++) {
siftup(A, i);
}
}
private
void
siftup
(
int
[] A,
int
k)
{
while
(k !=
0
) {
int
father = (k -
1
) /
2
;
if
(A[k]
>
A[father]) {
break
;
}
int
temp = A[k];
A[k] = A[father];
A[father] = temp;
k = father;
}
}
}
二、自顶向下siftdown
对数组中的每个元素，依次进行siftdown操作，可参考这个演示 demo。
siftdown：当前结点比父结点大，同较小的儿子结点交换，迭代操作直至当前结点大于两个儿子结点。
注：具体实现时需要注意索引的边界问题。
Java 实现
public
class
Solution
{
/**
*
@param
A: Given an integer array
*
@return
: void
*/
public
void
heapify
(
int
[] A)
{
if
(A ==
null
|| A.length ==
0
) {
return
;
}
// the heap array start at index 0, not index 1 (i = A.length / 2)
for
(
int
i = A.length /
2
-
1
; i
>
=
0
; i--) {
siftdown(A, i);
}
}
private
void
siftdown
(
int
[] A,
int
k)
{
while
(k
<
A.length) {
int
smallest = k;
if
(k *
2
+
1
<
A.length
&
&
A[k *
2
+
1
]
<
A[smallest]) {
smallest = k *
2
+
1
;
}
if
(k *
2
+
2
<
A.length
&
&
A[k *
2
+
2
]
<
A[smallest]) {
smallest = k *
2
+
2
;
}
if
(smallest == k) {
break
;
}
int
tmp = A[smallest];
A[smallest] = A[k];
A[k] = tmp;
k = smallest;
}
}
}