复旦大学961-数据结构-第三章-查找（5）优先队列与堆,堆的定义,堆的生成,调整算法；范围查询

傷城~ 2022-12-12 13:39 140阅读 0赞

[961全部内容链接][961]

### 文章目录 ###

*  优先队列的概念
 *  堆的定义
 *  堆的ADT定义
 *  堆的具体实现
 *   *  堆的插入和上滤调整算法
     *  堆的删除和下滤调整算法
     *  堆的生成
     *  范围查询
     *  完整代码

# 优先队列的概念 #

优先队列就是一个队列（Queue），但是它与普通的队列不一样的地方在于，它并不一定是先进先出，它需要再结合优先级，来决定谁先出。

比如，操作系统要决定当前CPU要给哪个程序使用，那么它就需要找到一个优先级更高的进程来分配CPU，而这些进程就是放在优先队列中的。操作系统只要选择优先级最高那个进行出队操作就行了。

优先队列的实现方式有很多种，最经典型的实现方式有以下三种：

1.  普通顺序表，可以使用数组实现，也可以使用链表实现。优点是入队很快，只需要在队尾插入元素即可，入队的时间复杂度为O(1)。但缺点是出队的时候要遍历表中的所有元素，找出优先级最高的元素进行出队，所以出队时间复杂度为O(n)
2.  有序顺序表，同样可以使用数组或链表实现。与1不同的时，这个表需要保持时刻有序。因为是有序的，所以每次出队只需要在取队首的元素即可，所以出队的时间复杂度为O(1)，缺点是入队的时候，要插入到合适的位置（插入排序原理），所以时间复杂度为O(n)。
3.  为了平衡1,2的优缺点。所以可以采用**二叉堆**这种数据结构来实现优先队列，这也是考试要考的内容，前面两种了解即可。堆的入队和出队操作时间复杂度都是O(log n)。它相比上面两种数据结构，既不会太快，也不会太慢，是个比较均衡的数据结构。

<table> 
 <thead> 
  <tr> 
   <th>数据结构</th> 
   <th>入队时间复杂度</th> 
   <th>出队时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>普通顺序表</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>有序顺序表</td> 
   <td>O(n)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>二叉堆</td> 
   <td>O(log n)</td> 
   <td>O(log n)</td> 
  </tr> 
 </tbody> 
</table>

# 堆的定义 #

二叉堆分为**最大堆**和**最小堆**（也可以叫**大根堆**和**小根堆**）。最大堆就是说数值越大优先级越高，而最小堆就是数值越小优先级越高。书上使用的最小堆，所以这里也默认堆指的是最小堆。

堆满足以下特定：

1.  堆是一棵**完全二叉树**
2.  堆中的每个子树的根节点的值都不大于其所有子孙节点。
3.  因为是完全二叉树，所以堆一般使用数组进行实现。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center]  
如图所示，这棵完全二叉树就是一个最大堆。其中每一个根节点都小于它的所有子孙节点。比如“13小于21,16,24…”，“16小于19,68”。

通过这样的堆，每次出队时，只需要取根节点，然后对最大堆进行调整。入队时，先将其放在最后一个节点，然后调整最大堆。

# 堆的ADT定义 #

public class BinaryHeap<AnyType extends Comparable<? super AnyType>> { 
    
        public BinaryHeap(int capacity /*堆的大小*/) { }
        
        private int currentSize;
        private AnyType[] array;
    
        public void insert(AnyType x) { }
    
        // 出队
        public AnyType deleteMin() { }
    }

基本上考试会考的也就是入队（insert）和出队（deleteMin）操作。书上给出了其他操作，应该不考，考了也能现写出来，比较简单。

# 堆的具体实现 #

## 堆的插入和上滤调整算法 ##

对于一个堆的插入，需要分两部：

1.  将要插入的元素放入完全二叉树的最后
2.  对该元素进行向上调整，又叫**上滤**（ShiftUp或PercolateUp）

具体方式如图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center 1]  
**注：堆与完全二叉树一样，数组0的位置一般不存放数据，为了方便计算。后面提到的计算均按照这个原则进行**

该例子为要在该完全二叉树（最小堆）中插入元素14，其中圆圈代表的是元素14。分为如下几步：

1.  将14放在完全二叉树的队尾。即 currentSize + 1 的位置。如图1
2.  将14与它的父节点（31）进行比较，若小于父节点，则与父节点交换位置
3.  不断地进行2过程，直到14处于堆顶或其父节点小于14.

代码如下：

public void insert(AnyType x) { 
            if (currentSize >= array.length - 1) { 
                // 判断队列是否已满，该句在书上为扩充队列
                throw new RuntimeException("队列已满");
            }
    
            currentSize++; // 堆元素数++
            array[currentSize] = x; // 将x放入堆的最后一个位置
            int i = currentSize; // 记录当前x所在的下标
            while (i != 1 // i 还没有到达堆顶
                    && x.compareTo(array[i / 2]) < 0 // x小于其父节点
            ) { 
                // 满足while的两个条件，继续进行上滤操作，即交换x与父节点的位置
                AnyType temp = array[i / 2];
                array[i / 2] = x;
                array[i] = temp;
                i = i / 2; // i移动到其父节点的位置
            }
        }

## 堆的删除和下滤调整算法 ##

堆的删除就是出队操作。每次选取堆顶的元素进行出队，出队之后要对整个二叉堆进行调整操作。调整有不同的做法，但必不可少的就是下滤操作。按照书中的过程如下：

1.  暂存堆顶元素，然后将二叉堆的最后一个元素放入堆顶并将其删除，记该元素为x。
2.  对x进行下滤操作，即对比x的左孩子和右孩子，将小的那个与x交换。
3.  不断地循环2过程，直到x的左右孩子比x都大或x到达堆底

需要注意的几点：

1.  对于下标为i的节点，它的左孩子为 (i×2)，右孩子为 (i×2+1)
2.  对于有n个节点的完全二叉树，i<=n/2时，i节点为分支节点，i>n/2时，为叶节点。

代码如下：

public AnyType deleteMin() { 
        if (currentSize <= 0) { 
            return null; // 删除失败，二叉堆为空
        }
    
        AnyType minResult = array[1];
        array[1] = array[currentSize];  // 将堆的最后一个元素换到栈顶
        array[currentSize] = null; // 将堆最后一个元素置空，这步骤可以省略。
        currentSize--;
    
        // 开始进行下滤操作
        percolateDown(1);
    
        return minResult;  // 返回最开始的堆顶元素
    }
    
    // 下滤操作，这个之所以抽出来，是因为构建堆的时候需要用
    private void percolateDown(int hole) { 
        int i = hole;// 记录当前下滤到的位置
        while (i<=currentSize/2) {  // 当下滤到叶子节点时，跳出循环
            int child = i*2; // 将child置为左孩子
            if (child + 1 <= currentSize  // 判断是否有右孩子，防止指针越界
                    && array[child].compareTo(array[child + 1]) > 0  // 判断左孩子与右孩子的大小
            ) { 
                child ++; //若右孩子比左孩子小，则将child指向右孩子，否则还是左孩子
            }
    
            if (array[child].compareTo(array[i]) < 0) { 
                // 如果当前节点的孩子比它小，则交换当前节点与它的孩子
                AnyType temp = array[i]; // 交换当前节点与其孩子节点
                array[i] = array[child];
                array[child] = temp;
            } else { 
                // 当前节点比它的左右孩子都小，则下滤完成，跳出循环。
                break;
            }
            i = child; // 当前节点向下，指向其孩子节点
        }
    }

## 堆的生成 ##

构建堆就是给定一个数组，然后根据该数组，生成一个二叉堆。过程如下：

1.  new一个新数组，然后把给定的数组元素复制过去
2.  对新数组进行堆构建。具体做法为: 从最后一个分支节点开始进行下滤操作（从后往前），直到进行堆顶为止。

代码如下：

public BinaryHeap(AnyType[] items) { 
    
        array = (AnyType[]) new Comparable[items.length + 100]; // +100是指给堆一些冗余空间。
    
        currentSize = items.length;
    
        // 将给定数组的数据复制到array中
        for (int i = 0; i < items.length; i++) { 
            array[i + 1] = items[i];
        }
    
        // 准备工作结束，开始进行Heapify
        for (int i = currentSize / 2; i > 0; i--) { 
            percolateDown(i);
        }
    }

构建堆的时间复杂度为O(n)

## 范围查询 ##

TODO

## 完整代码 ##

import java.util.Arrays;
    
    public class BinaryHeap<AnyType extends Comparable<? super AnyType>> { 
    
        public BinaryHeap(int capacity /*堆的大小*/) { 
            currentSize = 0;
            array = (AnyType[]) new Comparable[capacity + 1];
        }
    
        private int currentSize;
        private AnyType[] array;
    
        public BinaryHeap(AnyType[] items) { 
    
            array = (AnyType[]) new Comparable[items.length + 100]; // +100是指给堆一些冗余空间。
    
            currentSize = items.length;
    
            // 将给定数组的数据复制到array中
            for (int i = 0; i < items.length; i++) { 
                array[i + 1] = items[i];
            }
    
            // 准备工作结束，开始进行Heapify
            for (int i = currentSize / 2; i > 0; i--) { 
                percolateDown(i);
            }
        }
    
        public void insert(AnyType x) { 
            if (currentSize >= array.length - 1) { 
                // 判断队列是否已满，该句在书上为扩充队列
                throw new RuntimeException("队列已满");
            }
    
            currentSize++; // 堆元素数++
            array[currentSize] = x; // 将x放入堆的最后一个位置
            int i = currentSize; // 记录当前x所在的下标
            while (i != 1 // i 还没有到达堆顶
                    && x.compareTo(array[i / 2]) < 0 // x小于其父节点
            ) { 
                // 满足while的两个条件，继续进行上滤操作，即交换x与父节点的位置
                AnyType temp = array[i / 2];
                array[i / 2] = x;
                array[i] = temp;
                i = i / 2; // i移动到其父节点的位置
            }
        }
    
        // 出队
        public AnyType deleteMin() { 
            if (currentSize <= 0) { 
                return null; // 删除失败，二叉堆为空
            }
    
            AnyType minResult = array[1];
            array[1] = array[currentSize];  // 将堆的最后一个元素换到栈顶
            array[currentSize] = null; // 将堆最后一个元素置空，这步骤可以省略。
            currentSize--;
    
            // 开始进行下滤操作
            percolateDown(1);
    
            return minResult;  // 返回最开始的堆顶元素
        }
    
        // 下滤操作，这个之所以抽出来，是因为构建堆的时候需要用
        private void percolateDown(int hole) { 
            int i = hole;// 记录当前下滤到的位置
            while (i <= currentSize / 2) {  // 当下滤到叶子节点时，跳出循环
                int child = i * 2; // 将child置为左孩子
                if (child + 1 <= currentSize  // 判断是否有右孩子，防止指针越界
                        && array[child].compareTo(array[child + 1]) > 0  // 判断左孩子与右孩子的大小
                ) { 
                    child++; //若右孩子比左孩子小，则将child指向右孩子，否则还是左孩子
                }
    
                if (array[child].compareTo(array[i]) < 0) { 
                    // 如果当前节点的孩子比它小，则交换当前节点与它的孩子
                    AnyType temp = array[i]; // 交换当前节点与其孩子节点
                    array[i] = array[child];
                    array[child] = temp;
                } else { 
                    // 当前节点比它的左右孩子都小，则下滤完成，跳出循环。
                    break;
                }
                i = child; // 当前节点向下，指向其孩子节点
            }
        }
    
        // 检查堆是否正确
        public void checkHeap() { 
            for (int i = 1; i <= currentSize / 2; i++) { 
                if (array[i].compareTo(array[i * 2]) > 0) { 
                    throw new RuntimeException("Heap is error!");
                }
                if (i * 2 + 1 < currentSize && array[i].compareTo(array[i * 2 + 1]) > 0) { 
                    throw new RuntimeException("Heap is error!");
                }
            }
        }
    
        public static void main(String[] args) { 
    
            BinaryHeap<Integer> binaryHeap = new BinaryHeap<>(30);
            for (int i = 0; i < 20; i++) { 
                int r = (int) (Math.random() * 99);
                System.out.print(r + ", ");
                binaryHeap.insert(r);
            }
            System.out.println();
            System.out.println(Arrays.toString(binaryHeap.array));
            binaryHeap.checkHeap();
    
            System.out.print("依次删除: ");
            for (int i = 0; i < 20; i++) { 
                System.out.print(binaryHeap.deleteMin() + " ");
                binaryHeap.checkHeap();
            }
            System.out.println();
    
            Integer[] testArray = new Integer[20];
            for (int i = 0; i < 20; i++) { 
                int r = (int) (Math.random() * 99);
                testArray[i] = r;
            }
            BinaryHeap heap2 = new BinaryHeap<>(testArray);
            heap2.checkHeap();
            System.out.println(Arrays.toString(heap2.array));
        }
    }

[961]: https://blog.csdn.net/zhaohongfei_358/article/details/111414370
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/5636105e9e914cc09cc35e1117247f5b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/fdd21ac04911454c85c6772b2492c8ec.png