数据结构之——优先级队列（堆）

这里写目录标题

1.优先级队列
- 1.1概念
- 2. 优先级队列的模拟实现
- - 2.1堆的概念
  - 2.2堆的性质
  - 2.3堆的存储方式
  - 2.4堆的创建
  - - 2.4.1堆的向下调整
    - 2.4.2堆的向下调整的时间复杂度
    - 2.4.3以向下调整建堆的时间复杂度
    - 2.5堆的插入和删除
    - - 2.5.1堆的插入
      - 2.5.1.1元素插入法建堆的时间复杂度
        2.5.2堆的删除
        1.优先级队列
        
        1.1概念
        
        队列是一种先进先出(FIFO)的数据结构，但有些情下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该种场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。
        在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数
        据结构就是优先级队列(Priority Queue)。
        
        2. 优先级队列的模拟实现
        
        JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。
        
        2.1堆的概念
        
        如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<=K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
        
        2.2堆的性质
        
        (1)堆中某个节点的值总是不大于或不小于其父节点的值；
        (2)堆总是一棵完全二叉树。
        特别注意：若一个堆为大根堆，只表明堆的每个节点的值大于其左子节点和右子节点，至于左子节点和右子节点谁大谁小不确定。小根堆也是如此。举例如下：
        
        2.3堆的存储方式
        
        从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储,也就是用数组来存储。
        注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节
        点，就会导致空间利用率比较低。
        
        将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2；
        如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子；
        如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子。
        
        2.4堆的创建
        
        2.4.1堆的向下调整
        
        对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆呢？
        整个创建过程如下图所示：
        下面我们来思考一个问题，为什么要求从最后一棵子树开始，而不是从根节点开始向下调整呢？
        接下来文字叙述以下以向下调整的方式创建堆的过程（以创建大根堆为例）：
        
        让parent标记需要调整的节点，child标记parent的左孩子(注意：由于数组的种有效数据的个数是usedSize，因此堆的最后一个节点的下标是usedSize - 1,从而最先开始调整的子树的根节点下标是（usedSize - 1 - 1) / 2，parent如果有孩子一定先是有左孩子)；
        如果parent的左孩子存在，即:child < usdSize（其中usedSize是原始数组种有效数据的个数）。进行以下操作，直到parent的左孩子不存在。
        ①.parent右孩子是否存在，若存在找到左右孩子中最大的孩子，用child进行标记，若右孩子不存在，直接用 child标记左孩子。此时child记录的是parent孩子种的最大值的下标。
        ②.将parent值与child值比较，如果：
        parent值大于的child值，调整结束。否则：交换parent与child的值，交换完成之后，可能导致子树不满足堆的性质，因此需要继续向下调整，即parent = child；child = parent*2+1; 然后继续步骤2。
        注意:在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
        
        创建大根堆核心部分代码如下：
        
        public class Heap { public int[] elem; public int usedSize;//记录数组中有效数据的个数 public Heap(){ this.elem = new int[10]; } /** * 初始化elem数组 * @param array */ public void initHeap(int[] array){ for(int i = 0;i < array.length;i++){ elem[i] = array[i]; usedSize++; } } /** * 创建大根堆 */ public void creatBigHeap(){ for(int parent = (usedSize - 1 - 1)/2;parent >= 0;parent--){ shiftDown(parent,usedSize); } } /** * 线下调整 * @param parent * @param end */ private void shiftDown(int parent,int end){ int child = 2 * parent + 1; while(child < end){ if(child + 1 < usedSize && elem[child] < elem[child + 1]){ child++; } //到这里,child就是左右孩子最大值对应的下标 if(elem[child] > elem[parent]){ // 交换 swap(child,parent); parent = child; child = 2 * parent + 1; }else{ break;//左右孩子的最大值已经已经小于根节点的值，说明此时已经是大根堆了 } } } /** * 交换变量的值 * @param i * @param j */ private void swap(int i,int j){ int tmp = elem[i]; elem[i] = elem[j]; elem[j] = tmp; } }
        
        测试代码如下：
        
        public class Test { public static void main(String[] args) { int[] array = new int[]{ 27,15,19,18,28,34,65,49,25,37}; Heap heap = new Heap(); heap.initHeap(array); heap.creatBigHeap(); } }
        
        运行结果如下：
        对比我们下图的预期结果，说明代码没有问题。
        
        2.4.2堆的向下调整的时间复杂度
        
        最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为O(log2n)。
        
        2.4.3以向下调整建堆的时间复杂度
        
        因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
        因此：建堆的时间复杂度为O(n)
        
        2.5堆的插入和删除
        
        2.5.1堆的插入
        
        堆的插入总共需要两个步骤：
        
        先将元素放入到底层空间中(注意：空间不够时需要扩容)；
        将最后新插入的节点向上调整，直到满足堆的性质。
        
        如图所示是一个小根堆的插入过程：
        代码实现(以小根堆为例)：
        
        /** * 堆的插入 * @param val */ public void offer(int val){ //1.判断数组是否满了，如果满了，需要扩容 if(isFull() == true){ elem = Arrays.copyOf(elem,2*elem.length);//2倍扩容 } //2.插入元素 elem[usedSize] = val; usedSize++; //3.向上调整 shiftUp(usedSize-1); } /** * 向上调整 * @param child */ public void shiftUp(int child){ int parent = (child-1)/2; while(child > 0){ if(elem[child] < elem[parent]){ swap(parent,child);//交换下标parent和child处元素的值 child = parent; parent = (child - 1) / 2; }else{ break; } } } /** * 判断数组元素是否满 * @return */ public boolean isFull(){ return usedSize == elem.length; }
        
        由堆的插入我们可以得到启发，在建堆的过程中我们可以边插入元素边调整，即用元素插入法建堆（也叫向上调整法）。
        
        2.5.1.1元素插入法建堆的时间复杂度
        
        2.5.2堆的删除
        
        注意：堆的删除一定删除的是堆顶元素。具体如下：
        
        将堆顶元素对堆中最后一个元素交换
        将堆中有效数据个数减少一个
        对堆顶元素进行向下调整
        
        如图所示是一个大根堆的删除过程：
        代码实现：
        
        /** * 删除堆顶元素 * @return */ public int poll(){ int tmp = elem[0];//标记堆顶元素 swap(0,usedSize-1);//交换堆中首末元素 usedSize--;//有效数据值-1 shiftDown(0,usedSize);//堆顶元素向下调整 return tmp; }
        
        注意：上述代码执行完毕后，数据10仍在数组中，但是由于我们进行了usdSize-1的操作，我们认为堆中的数据实际上已经不包含10了，从而达到删除堆顶元素的目的。

节点 在这里

相关推荐

