本文主要是介绍数据结构中的堆--堆的定义、调整堆、建堆、自定义堆，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、堆的定义
1.结构特点
堆（数据结构）和Java语言中提到的堆没有一点关系。
逻辑上：完全二叉树
物理上：数组
堆是一种顺序存储结构（采用数组方式存储），仅仅是利用完全二叉树的顺序结构的特点进行分析。
2.结点下标计算公式（根节点从0开始）
已知二叉树根结点的下标是root,那么它左孩子的下标left=2*root+1，右孩子的下标right=2*root+2。
已知孩子结点的下标（不区分左右）为child，那么双亲的下标为（child-1)/2。
如果从1开始，则已知root，则左孩子节点left=2*root+1,right=2*root+2。已知child，则其根结点root=child/2.
3.堆的定义和性质
将满足根的值小于等于所有子树结点的值，称为小堆；根的值大于等于所有子树结点的值称为大堆。
堆的作用：找最值。
4.练习
（1）{9，10，13，17，21，14，13，22} 小堆
（2）{10，8，3，8，8，2，1，7，6} 大堆
（3）{10，7，6，5，5，7，3，4，2} 既不是大堆也不是小堆
二、调整堆
1.向下调整（堆化）
向下调整的前提：对于一棵完全二叉树，除了一个位置外，所有其它位置都已经满足堆的性质了。
给定一个表示完全二叉树的数组和要调整的下标，如果该结点下标是叶子结点，那么不需要调整。如果不是叶子结点，这里假设是大堆，则调整步骤为：
1）计算出它的左右孩子下标，并判断是否越界。left=2*root+1,right=2*root+2. 若left>array.length，说明越界；否则没有越界。
2）找出它的左右孩子的较大值。右孩子结点可能没有，较大值是右孩子的条件是：right<array.length&&array[right]>array[left]。不满足这个条件可以认为较大值结点是左孩子。
3）将较大值和根结点值进行比较，如果根结点值较大，则不需要调整，直接返回；否则，继续向下调整。将要调整的结点修改为较大值的下标。
package heap;public class TestHeap {//递归写法private static void adjustDown(int[] array,int root){//1.计算左右下标int left=2*root+1;int right=2*root+2;//判断是否越界if(left>=array.length){return;}//2.找左右孩子的最大值下标int max=left;if(right<array.length&&array[right]>array[left]){max=right;}//3.和根结点的值比较if(array[root]>=array[max]){return;}//交换int temp=array[root];array[root]=array[max];array[max]=temp;//继续向下调整adjustDown(array,max);}public static void main(String[] args) {int[] array=new int[]{10,7,6,5,5,7,3,4,2};//6不符合，调整的下标为2adjustDown(array,2);for(int item:array){System.out.print(item+" ");}}
}
非递归写法，终止条件仍然为越界判断。因此非递归的步骤为：
1）先假定没有越界，计算出最大坐标为max=2*root+1.
2）判断是否满足终止条件（max>=array.length),如果满足，则终止；不满足，则计算右孩子的下标。
3）找出较大的孩子下标
4）将较大的孩子值与根的值进行比较，如果根的值也大于孩子的值，则循环终止。否则进行下一步。
5）交换两个下标的值。并修改新的root和max，root=max,max=2*root+1。
package heap;public class TestHeap {//非递归写法private static void adjustDownNoR(int[] array,int root){//int max=2*root+1;while(max<array.length){if(max+1<array.length&&array[max+1]>array[max]){max=max+1;}//比较根节点的值与max的值if(array[root]>array[max]){break;//循环终止}//交换int temp=array[max];array[max]=array[root];array[root]=temp;//重新赋值root=max;max=2*root+1;}}public static void main(String[] args) {int[] array=new int[]{10,7,6,5,5,7,3,4,2};//6不符合，调整的下标为2adjustDownNoR(array,2);for(int item:array){System.out.print(item+" ");}}
}
如果是小堆的向下调整，代码为：
package heap;public class SmallHeap {private static void adjustDown(int[] array,int index){//1.计算左右下标int left=2*index+1;int right=2*index+2;//判断是否越界if(left>=array.length){return;}//2.找左右孩子中的较小值int min=left;if(right<array.length&&array[right]<array[left]){min=right;}//3.比较根结点的值和较小值if(array[index]<=array[min]){return;}//交换int temp=array[min];array[min]=array[index];array[index]=temp;adjustDown(array,min);}private static void adjustDownNoR(int[] array,int index){int min=2*index+1;while(min<array.length){//终止条件//找较小值if(min+1<array.length&&array[min+1]<array[min]){min=min+1;}//比较if(array[index]<=array[min]){return;}//交换int temp=array[min];array[min]=array[index];array[index]=temp;//重新赋值index=min;min=2*index+1;}}public static void main(String[] args) {int[] array=new int[]{13,8,10,13,12,11,12,14};adjustDown(array,0);for(int item:array){System.out.print(item+" ");}System.out.println();adjustDownNoR(array,0);for(int item:array){System.out.print(item+" ");}}
}
2.向上调整
和向下调整不同的是，每次比较的对象变为双亲结点值。终止条件为比不过或者到达最顶端（没得比了）。假设为大堆，步骤为：
1）计算parent。parent=(index-1)/2
2）判断parent是否大于0，如果大于，进入下一步；小于，说明越界，当前结点已经是根结点，不能继续向上调整。
3）比较双亲结点的值和要调整的结点的值。如果双亲结点值较大，则不用比了，跳出循环；否则交换两个对应下标的值。
4）修改index和parent，继续下一次循环。index=parent,parent=(index-1)/2。
//大堆的向上调整 根结点值>=孩子结点private static void adjustUp(int[] array,int index){//计算双亲结点int parent=(index-1)/2;while(parent>0){//比较值if(array[parent]>=array[index]){break;}//交换值int temp=array[parent];array[parent]=array[index];array[index]=temp;//修改值，进行下一次循环index=parent;parent=(index-1)/2;}}public static void main(String[] args) {int[] array=new int[]{10,7,6,5,5,7,3,4,2};//6不符合，调整的下标为2adjustUp(array,5);for(int item:array){System.out.print(item+" ");}}三、建堆
叶子结点本来就是一个堆。对每一个根结点，只要满足它的左右子树都是堆即可。因此从最后一个非叶子结点开始，依次进行向下调整堆，直到根结点为止，此时整个二叉树就是一个堆。
怎么找最后一个非叶子结点？最后一个非叶子结点就是最后一个结点的双亲，下标即(array.length-1-1)/2=(array.length-2)/2.
package heap;public class TestHeap {//大堆的递归写法private static void adjustDown(int[] array,int root){//1.计算左右下标int left=2*root+1;int right=2*root+2;//判断是否越界if(left>=array.length){return;}//2.找左右孩子的最大值下标int max=left;if(right<array.length&&array[right]>array[left]){max=right;}//3.和根结点的值比较if(array[root]>=array[max]){return;}//交换int temp=array[root];array[root]=array[max];array[max]=temp;//继续向下调整adjustDown(array,max);}//建大堆private static void createHeap(int[] array){for(int i=(array.length-2)/2;i>=0;i--){adjustDown(array,i);}}public static void main(String[] args) {int[] array=new int[]{4,3,2,1,6,9,15,40};//6不符合，调整的下标为2{10,7,6,5,5,7,3,4,2}createHeap(array);for(int item:array){System.out.print(item+" ");}}
}
四、自定义一个堆类
package com.xunpu.datastruct;import java.util.Arrays;class Heap{private int[] array;private int size;Heap(){this(new int[0]);}Heap(int[] array){this.array=new int[10000];for(int i=0;i<array.length;i++){this.array[i]=array[i];}this.size=array.length;createHeap(this.array,this.size);}/**** @return 返回最值*/int top(){return array[0];}//删除堆顶元素，然后让最后一个元素赋值给堆顶，然后向下调整int pop(){int v=array[0];array[0]=array[this.size-1];this.size--;heapify(array,size,0);return v;}//在最后一个位置的后面添加堆元素，然后向上调整void push(int v){array[size++]=v;adjustUp(array,size,size-1);}//获取堆中元素的个数public int getSize(){return this.size;}//大堆private void adjustUp(int[] array, int size, int index) {/*** 1.array[index]<=array[(index-1)/2]比不过双亲结点的值* 2.index==0*/while(index>0){int parent=(index-1)/2;if(array[parent]>=array[index]){break;}//交换int t=array[parent];array[parent]=array[index];array[index]=t;//继续向上调整index=parent;}}/*** 大堆* 向下调整（堆化）* 必须满足可以向下调整的前提：只有一个位置不满足堆** @param tree 看成完全二叉树的下标* @param index 要调整的下标*/public static void heapify(int[] tree, int size,int index) {/*** 1.判断index位置是不是叶子结点* 完全二叉树，只要判断有没有左孩子* 转化为数组下标越界的问题去判断*/int left = 2 * index + 1;if (left >= size) {return;}/*** 不是叶子结点，意味着一定有左孩子，但不一定有右孩子* 2.找到最大的一个孩子* 1）没有右孩子 左孩子最大* 2）有右孩子* 左边大 左孩子大* 右边大 右孩子大*/int right = 2 * index + 2;int max = left;if (right < size && tree[right] > tree[left]) {//，只有下标没有越界，才能访问数组的值max = right;}/*** 3.和要调整的结点的值进行比较* 如果要调整的结点值比较大，满足堆的性质，不需要调整* 否则，交换数组中两个下标的值* 并且，继续以max作为下标，进行向下调整*/if (tree[index] >= tree[max]) {return;}//根的值较小，先交换int t = tree[max];tree[max] = tree[index];tree[index] = t;//继续向下调整heapify(tree, size,max);}//建堆 细算：O(n) 粗略：O(n*log(n))public static void createHeap(int[] array,int size) {//从最后一个非叶子结点的下标开始，一路向下调整至根位置。[(array.length-2)/2,0]for (int i = (size - 2) / 2; i >= 0; i--) {heapify(array, size,i);}}}
这篇关于数据结构中的堆--堆的定义、调整堆、建堆、自定义堆的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
