网站开发实习计划模板抖音品牌推广方案

堆（Heap）：堆可以看做是一颗用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。

堆的特性

1.堆是完全二叉树，除了树的最后一层节点不需要是满的，其它的每一层从左到右都是满的，如果最后一层节点不是满的，那么要求左满右不满。

2.它通常用数组来实现

具体方法就是将二叉树的节点按照层级顺序放入数组中，根结点在位置1，它的子节点在位置2和3，而子节点的子节点则分别在位置4、5、6和7，以此类推。

比如，一个节点的位置为k，则它的父节点的位置为k/2，而它的两个子节点的位置分别为2k和2k+1。这样，在不使用指针的情况下，可以通过数组的索引在树中上下移动：向上一层就令k为k/2，向下一层就令k等于2k或者2k+1.

insert插入方法的实现

由于堆是用数组完成数据元素的存储，由于数组的底层是一串联系的内存地址，所以从数组索引依次往后存放数据，但堆中的元素的顺序是有要求的，每一个结点的数据要大于等于它的两个子节点的数据（注意这点和树的方式不同），所以每次插入一个元素，都会使得堆中的数据顺序变乱，这个时候就需要额外的方法将刚插入的数据放入和合适的位置。

所以，如果往堆中插入新元素，我们只需要不断的比较新节点k和它的父节点k/2的大小，然后根据结果完成元素的交换，来实现堆的有序调整。

代码实现：

//判断堆中索引i处的元素是否小于索引j处的元素private boolean less(int i,int j){return items[i].compareTo(items[j])<0; //i如果小于j compaerto结果就为负数 --那么就返回true}//交换堆中的i索引和j索引处的值private void exchange(int i,int j){T temp=items[i];items[i]=items[j];items[j]=temp;}/*** 插入元素方法*/public void insert(T t){items[++N]=t; //先++的原因是 此处数组索引0处 不存储元素 从索引1开始swim(N);}/*** 元素浮动方法* 时元素上浮到合适的位置*/public void swim(int k){while (k>1){//索引1表示根节点  如果浮动到根节点 那么就不需要再浮动了if (less(k/2,k)){ //如果插入元素比父节点大那么就需要交换//父节点比子节点小 那么就需要交换exchange(k/2,k);}k=k/2; //然后使k上浮一层 进入下一次判断}}

deleteMax删除最大值方法的实现
由堆的特性可以知道，索引1处的元素，也就是根节点就是最大的元素，当我们把根节点的元素删除后，需要有一个新的根节点出现，这时候可以暂时把堆中的最后一个元素放到索引1处暂时充当根节点，但是这样有可能不满足堆的有序性要求，这时候就需要通过元素下沉让新的根节点放入到合适的位置。

所以删除最大元素后，只需要将最后一个元素放到索引1处，并不断拿当前节点k与它的子节点2k和2k+1比较，然后与较大者交换位置，即可完成堆的有序性调整。
代码实现：

/*** 删除最大值  也就是根节点*/public T deleteMax(){T max=items[1];  //索引1处为根节点exchange(1,N); //索引1根节点  与最后一个节点交换items[N]=null;N--;slink(1);return max;}/*** 元素下沉**/public void slink(int k){while (2*k<=N){ //当2*k>N时 就表示该k节点没有子节点了 跳出循环int max; //找到两个子节点中最大的if (2*k+1<=N){ //如果存在右子节点if (less(2*k,2*k+1)){//比较两个子节点max=2*k+1;}else {max=2*k;}}else { //如果不存在右子节点 那么只有左子结点的情况max=2*k;}//到此两个子节点中的较大者已经比较出 然后将将其比较 如果需要交换的节点比较大者要大 那么就可以结束循环if (!less(k,max)){return;}//如果当前节点 比大子节点小 那么就进行交换exchange(k,max);k=max;}}

测试结果：

public static void main(String[] args) {Heap<String> heap = new Heap<String>(20);heap.insert("A");heap.insert("B");heap.insert("C");heap.insert("D");heap.insert("E");heap.insert("F");heap.insert("G");
//        heap.insert("A");
//        heap.insert("T");
//        heap.insert("P");
//        heap.insert("R");String del;while((del=heap.deleteMax())!=null){System.out.print(del+",");}}
//运行结果
G,F,E,D,C,B,A,