如何运营一个品牌的推广_花火视频影视大全免费观看_视频号直播推广二维码_班级优化大师手机版下载(免费)

目录

堆的概念：

        堆向下调整：

        堆的插入元素，使用了向上调整：

        堆删除元素：

---

堆的概念：

        堆通常有两种类型：

        大根堆和小根堆。最大堆的父节点值大于等于子节点，而最小堆则是父节点值小于子节点。堆是一种特殊的完全二叉树。

        比如：

        大根堆：

        

         小根堆：

        

         

        堆向下调整：

                比如有个数组：

 int[] array = {27,15,19,18,28,34,65,49,25,37};TestHeap testHeap = new TestHeap();testHeap.init(array);testHeap.createHeap();

        原图：

        

                 根据其数据的大小调整成大根堆，则：

public class TestHeap {//存储数据public int[] elem;//存放有效数据的个数public int usedSize;public TestHeap() {elem = new int[10];}public void init(int[] array) {for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedSize++;}}public void swap(int a,int b) {int ret = elem[a];elem[a] = elem[b] ;elem[b] = ret;}public void createHeap() {for (int i = (usedSize-1-1) / 2; i >= 0 ; i--) {siftDown(i,usedSize);}}public void siftDown(int parent,int k) {int child = 2 * parent + 1;while(child < k) {if(child + 1 < k && elem[child] < elem[child + 1]) {child++;}if(elem[child] > elem[parent]) {swap(child,parent);parent = child;child = 2 * parent + 1;}else {break;}}}
}

        程序运行得到结果：

        

        

         期望得到的结构：

         

         

         可以看到，结果与期望是一致的。

         这里，createHeap 方法通过从底部的子树第一个父节点开始，一直到树的根节点0序号，不断向下调整子树的堆，所以这样也称为向下调整。

        过程中，child 作为孩子结点，要小于有效元素个数usedSize，并且，要寻找得到左孩子和右孩子最大的一个与根结点parent对比，符合条件再交换值，再往下调整。

        

        堆的插入元素，使用了向上调整：

        比如我们要插入一个元素val：

        代码实现：

public void offer(int val) {//容量不够则扩容if(isFull()) {elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize] = val;//向上调整siftUp(usedSize);usedSize++;}public void siftUp(int child) {int parent = (child-1) / 2;while(parent >= 0) {if(elem[child] > elem[parent]) {//交换swap(child,parent);child = parent;parent = (child-1) / 2;}else {break;}}}public boolean isFull() {return elem.length == usedSize;}

        siftUp方法中，因为要插入的堆本身就是一种数据结构，这里当作是大根堆，插入元素后仍然要保持是大根堆，则刚好用当前usedSize作为插入元素的下标给到 child ，只要判断 elem[parent] 和 elem[child] 的大小关系即可。再通过向上调整实现整棵树插入元素后还是大根堆。

        

        堆删除元素：

        代码实现：

 public void poll() {//判断是否为空if(isEmpty()) {//抛异常return;}swap(0,usedSize-1);usedSize--;siftDown(0,usedSize);}public boolean isEmpty() {return usedSize == 0;}

         因为删除的是0下标的元素，我们的方法是通过把0下标的元素与最后一个元素下标交换，之后再通过从根节点（0下标）开始向下调整。因为向下调整前 usedSize 减一 了，不会把要删除的数据操作了，当之后要插入新元素会将其覆盖。