数据结构：Heap

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);

    }

}