Heap就是堆，在数据结构里也是比较重要的一种，它的定义是：一种完全二叉树的树形结构，有两种，最大堆max-heap和最小堆min-heap， 最大堆的定义就是父节点必须是它所有子节点中最大的，反之最小堆亦然。
为何要创建这样的堆结构呢，这其实还是为了方便存储一些数据，可以马上找到最大，最小值，和优先级队列很类似。
这里我们来看如何从给定的数组建立一个最大堆。
以数组 【4，10，3，5，1】为例，创建一个最大堆。
首先要回忆一下完全二叉树的几个属性：
-根节点是index为0的数组元素。
-第i个节点的左子节点的index是（2i+1）
-第i个节点的右子节点的index是（2i+2）
-第i个节点的父节点index是（i-1）/2
那么我们如何才能把一个初始化为【4，10，3，5，1】的完全二叉树构建成一个堆序列呢，
如下图是一个初始化的完全二叉树结构：
我们可以清楚的看到这是不符合堆定义的，那么怎么做呢，第一个非常暴力的想法是，从最后一个元素开始，对每个元素开始做heapify，即先确保当前节点及其子树是一个堆，然后再向前倒序遍历heapify所有节点，比如，我们从1开始，1没有子节点，显然单独的1是满足heap要求的，同理，5，3，那再看10，显然以10为父节点的子树10，5，1满足条件，
再看4，以4为父节点的子树4，10，3不满足条件，应交换10<->4，交换后，再看4，5，1，也应交换4，5,至此才算完全符合heap的要求了。
但是上面的情况可以继续优化，因为叶子节点其实不用去调整，只用调整非叶子节点即可，
比如4，1不用去比较也是符合堆属性的（这里4，1只两个节点，但是如果这个树非常庞大，最后一层的子节点非常多的情况下，优化就很有必要）。
因此我们可以从倒数第一个非叶子节点开始，以此和它的父节点比较大小：
最后一个节点的index是n-1,最后一个节点的父节点序列号是：（n-1-1）/2，
从起初的10开始heapify。
下面我们用代码来实现上面的操作：
package zexin;
public class Heap {
void heapify(int arr[],intn, int i){
int largest= i;
int left
= 2 * i + 1;
int right
= 2 * i + 2;
if(left < n&&arr[left] > arr[largest])
largest = left;
if(right < n && arr[right] > arr[largest])
largest = right;
if(largest!= i){
int temp= arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr,n,largest);
}
}
void buildHeapByArray(int arr[],intn){
int startIdx
= ( n / 2 ) - 1;
for(int i = startIdx;i>= 0;i--){
heapify(arr,n,i);
}
}
void printHeap(int arr[],intn){
System.
out.println("array representation of heap is: ");
for(int i=0;i
System.
out.print(arr[i]+" ");
}
}
test:
package zexin;
import java.util.*;
public class Main {
public static void main(String[] args) {
// write your code here
int arr[] = {4,10,3,5,1};
int n = arr.length;
Heap hp =
new Heap();
hp.buildHeapByArray(arr,arr.
length);
hp.printHeap(arr,arr.
length);
}
}
网友评论