【优先级队列 之 堆的实现】

---

前言

---

优先级队列 PriorityQueue

概念：对列是先进先出的的数据结构，但有些情况，数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列。所以像这种情况用队列不太合适：在手机上玩游戏时，如果有来电，系统应该优先处理打进来的电话。以前是来电显示充满整个画面，现在变成了一个小窗。

优先队列的模拟实现

PriorityQueue的底层使用了堆这种数据结构（PriorityQueue底层实现是一个完全二叉树，完全二叉树又分为大根堆和小根堆）

堆

概念：
小根堆：根节点比左右孩子都小。只考虑根和左右节点的关系，不考虑左右节点的哪个大。
大根堆：根节点比左右孩子都大

堆的储存方式

将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设为节点在数组中的下标，则有: 如果为0，则表示的节点为根节点，否则节点的双亲节点为(i 1)/2
●如果2i+ 1小于节点个数，则节点的左孩子下标为2 门中1,否则没有左孩了
●如果2i+2小于节点个数，则节点的右孩子下标为21+ 2,否则没有右孩子

堆的创建

1. 让parent标记需要调整的节点，child标记parent的左孩子(注意: parent如果有孩子一 定先是有左孩子)
2. 如果parent的左孩子存在，即:child < size,进行以下操作， 直到parent的左孩子不存在
   parent右孩子是否存在，存在找到左右孩子中最大的孩子，让child进行标记
3. 将parent 与较大的孩子child比较,如果:
   parent小于较大的孩子child,交换parent与较大的孩子child,交换完成之后，parent中小的元素向下移动，并继续向下调整，即parent = child; child = parent*2+1;然后继续
   否则:退出循环。

public class TestHeap {//创建一个数组public int[] elem;public int useSize;//有效元素//构造方法给elem分配内存public TestHeap() {this.elem = new int[10];}//初始化elem数组，给elem传入元素public void initElem(int[] array){for (int i = 0; i < array.length; i++) {elem[i] = array[i];useSize++;}}/*** 创建大根堆的代码*/public void createHeap(){for (int parent =(useSize-1-1)/2 ; parent >=0 ; parent--) {siftDown(parent,useSize);}}/*** 向下调整* @param parent* @param len*///让child标记根的左孩子，如果左孩子大于数组长度则进行下面操作// 如果右孩子小于长度并且左孩子的值小于右孩子的值，让左孩子移到右孩子上private void siftDown(int parent,int len){int child = 2*parent+1;while(child < len){if (child+1 < len && elem[child] < elem[child+1]){child = child+1;}//此时child保存的是孩子节点中最大的值//如果左孩子大于根节点，两者的值交换。if (elem[child] > elem[parent]) {//和根节点交换int tmp = elem[child];elem[child] = elem[parent];elem[parent] = tmp;//交换完再换位置parent = child;//根节点移到孩子节点上child = 2*parent+1;//孩子节点再往下移}else{break;}}}
}public class Test {public static void main(String[] args) {TestHeap testHeap = new TestHeap();int[] array={27,15,19,18,28,34,65,49,25,37};testHeap.initElem(array);testHeap.createHeap();System.out.println("========");}
}

建堆的时间复杂度

因此：建堆的时间复杂度是0（N）

堆的插入与删除

堆的插入：

    private void swap(int i,int j){int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}//向上调整public void push(int val){if(isFull()){elem = Arrays.copyOf(elem,elem.length*2);}elem[usedSize] = val;siftUp(usedSize);usedSize++;}public boolean isFull(){return usedSize == elem.length;}public void siftUp(int child){int parent = (child-1)/2;while(child > 0){if (elem[child] > parent){swap(child,parent);child = parent;parent = (child-1)/2;}else{break;}}}

堆的删除
注意：这里的删除指的是删除堆顶的元素

1. 将0下标的的堆顶元素和堆的最后一个元素交换
2. 将堆的有效个数usedSize–
3. 对堆进行向下调整

    //删除堆顶元素public int pop(){if (empty()){return -1;}int oldVal = elem[0];swap(0,usedSize-1);usedSize--;siftDown(0,usedSize);return oldVal;}public boolean empty(){return usedSize == 0;}

总结

本章节学习如何实现一个堆，如何运用到向上调整，向下调整。