23、数据结构与算法 - 实战:优先队列和堆

优先队列(Priority Queue)是一种数据结构,它支持插入(Insert)操作和删除最小值(DeleteMin)或删除最大值(DeleteMax)并返回删除元素操作。
优先队列的这些操作等价于队列的EnQueue和DeQueue操作。
区别在于,对于优先队列,元素进入队列的顺序可能与其被操作的顺序不同。
简单来说就是优先队列不一定满足先入先出的原则,而是根据元素的优先级来进行操作。

如果最小键值元素拥有最高的优先级,那么这种优先队列叫作升序优先队列(即总是先删除最小的元素)
如果最大键值元素拥有最高的优先级,那么这种优先队列叫作降序优先队列(即总是先删除最大的元素)

  • 优先队列的主要操作
  • 优先队列是元素的容器,每个元素有一个相关的键值。
  • Insert(key, data):插入键值为key的数据到优先队列,元素以其key进行排序。
  • DeleteMin/DeleteMax:删除并返回最小/最大键值的元素
  • GetMin/GetMax:返回最小/最大键值的元素,但不删除该元素
  • 第k最小/最大:返回优先队列中键值为第k个最小/最大的元素
  • 大小(Size):返回优先队列中的元素个数
  • 堆排序(Heap Sort):基于键值的优先级将优先队列中的元素进行排序

优先队列的实现主要讨论二叉堆的实现方式

堆(Heap)是一棵具有特定性质的二叉树。
堆的基本要求是堆中所有节点的值必须大于等于(或小于等于)其孩子节点的值。
堆还要求当h>0时,所有的叶子节点都处于第h或h-1层(其中h为树的高度),也就是说堆是一棵完全二叉树。

        7                           1
       / \                         / \
      3   6                       5   2
     / \ /                       / \ / \
    1  2 4                      6  1 1  3
该树是堆,每个节点元素都        这棵树不是堆,因为5大于其右孩子1
大于其孩子节点的元素

堆的类型:
最小堆:节点值必须小于等于其孩子节点的值
最大堆:节点值必须大于等于其孩子节点的值

            1                           17
           / \                         / \
          15  2                       13  6
         / \ / \                     / \ / \
        16 174  3                   1  4 2  3
         最小堆                        最大堆

在二叉堆(Binary Heap)中,每个节点最多有两个孩子。一般在优先队列中二叉堆称作堆(Heap)。
堆的表示:一般使用数组来存储堆中的元素。例如,最大堆可以表示如下:

data    17  13  6   1   4   2   3
        -------------------------
index   0   1   2   3   4   5   6

堆相关的代码,如下:

/**
 * 最大堆
 */
public class Heap {
   
     

    // 堆元素数组
    private int[] array;        

    // 堆中元素的个数
    private int size;

    // 堆的大小
    private int capacity;

    // 堆的类型 
    private String heap_type;

    /**
     * 构造方法:根据大小和类型创建堆
     * 
     * @param capacity 堆的大小
     * @param heap_type 堆的类型
     */
    public Heap(int capacity, String heap_type) {
        this.size = 0;
        this.capacity = capacity;
        this.heap_type = heap_type;
        this.array = new int[capacity];
    }

    /**
     * 根据节点的位置获取双亲结点的的位置
     * 
     * 对于第i个位置上的节点,则其双亲节点在(i-1)/2位置上
     * @param index 节点的位置
     * @return 双亲结点的位置
     */
    public int getParentByIndex(int index) {
        if ((index < 0) || (index >= this.size)) {
            return -1;
        }
        return (index - 1)/2;
    }

    /**
     * 根据节点位置获取左孩子节点的位置
     * 
     * 对于第i个位置上的节点,则其左孩子节点在2*i+1位置上
     * @param index 节点位置
     * @return 左孩子节点位置
     */
    public int leftChild(int index) {
        int left = 2 * index + 1;
        if (left >= this.size) {
            return -1;
        }
        return left;
    }

    /**
     * 根据节点位置获取右孩子节点的位置
     * 
     * 对于第i个位置上的节点,则其右孩子节点在2*i+2位置上
     * @param index 节点位置
     * @return 右孩子节点位置
     */
    public int rightChild(int index) {
        int right = 2 * index + 2;
        if (right >= this.size) {
            return -1;
        }
        return right;
    }

    /**
     * 获取最大元素
     * 
     * 最大堆中的最大元素就是根节点,所以其存储在数组0号位置
     * @return 最大元素
     */
    public int getMax() {
        if (this.size == 0) {
            return -1;
        }
        return this.array[0];
    }

    /**
     * 堆化当前元素
     * 
     * 当插入或删除一个堆元素时,它可能不满足堆的性质。
     * 在这种情况下就需要调整堆中的元素使之重新变成堆。这一过程叫作堆化(heapifying)
     * 在最大堆中,要堆化一个元素,需要找到其孩子节点中的最大值,然后交换元素,重复该过程直到每个节点都满足堆的性质。
     * 这一过程是自顶向下,所以也叫作向下渗透。
     * @param index 当前元素的位置
     */
    public void percolateDown(int index) {
        int max = 0;
        /* 先获取当前节点的孩子节点 */
        int left = leftChild(index);
        int right = rightChild(index);
        /* 比较当前节点与其孩子节点的值 */
        if ((left != -1) && (this.array[left] > this.array[index])) {
            max = left;
        } else {
            max = index;
        }
        if ((right != -1) && (this.array[right] > this.array[max])) {
            max = right;
        } 
        /* 如果当前节点不是最大值则交换元素 */
        if (max != index) {
            int temp = this.array[index];
            this.array[index] = this.array[max];
            this.array[max] = temp;
            /* 递归堆化 */
            percolateDown(max);
        } 
    }

    /**
     * 删除堆元素
     * 
     * 删除堆元素,只需要从根节点删除元素。
     * 删除根节点后,将堆的最后一个元素复制到根节点位置,然后删除最后一个元素。
     * 当用最后一个元素替换根节点后,可能导致二叉树不满足堆的性质,所以需要堆化根节点元素。
     * @return 删除的元素
     */ 
    public int deleteMax() {
        /* 先判断堆是否存在 */
        if (this.size == 0) {
            return -1;
        }
        // 获取根节点元素
        int data = this.array[0];
        // 将最后一个元素复制到第一个元素位置
        this.array[0] = this.array[this.size - 1];
        // 堆的大小减小
        this.size--;
        /* 堆化根节点元素,即数组第一个位置的元素 */
        percolateDown(0);
        // 返回删除的元素
        return data;
    }

    /**
     * 插入元素
     * 
     * 堆的大小增加一
     * 将新元素放到堆的尾部
     * 从下至上的堆化该元素,也称作向上渗透
     * @param data 插入的新元素
     */
    public void insert(int data) {
        /* 如果数组容量不够则扩容 */
        if (this.size == this.capacity) {
            resizeHeap();
        }
        // 数组元素个数加一
        this.size++;
        // 新元素的位置
        int index = this.size - 1;
        /* 堆化元素,向上渗透 */
        while ((index >= 0) && (data > this.array[(index - 1) / 2])) {
            // 当新元素大于其双亲结点,复制双亲结点到新元素位置
            this.array[index] = this.array[(index - 1) / 2];
            // 更新新元素位置
            index = (index - 1) / 2;
        }
        this.array[index] = data;
    }

    /**
     * 清空堆
     */
    public void destroyHeap() {
        this.size = 0;
        this.array = null;
    }

    /**
     * 数组建堆
     * 
     * 先将数组元素插入空堆中,不考虑堆的性质。
     * 因为叶子节点总是满足堆的性质,无需关注它们。
     * 叶子节点元素总是在最后面,因此要对给定的数组建堆,只需要堆化叶子节点即可。
     * 
     * 堆的最后一个元素所处的位置为size-1,通过最后一个元素的双亲节点就能找到第一个非叶子节点((size-1)-1)/2。
     * @param heap 堆
     * @param array 数组
     */
    public void buildHeap(Heap heap, int[] array) {
        // 获取数组的大小
        int n = array.length;
        /* 如果堆不存在则返回 */
        if (heap == null) {
            return;
        }
        /* 如果堆的容量不够则扩容 */
        while (n > this.capacity) {
            heap.resizeHeap();
        }
        /* 先将数组元素存入堆中 */
        for (int i = 0; i < n; i++) {
            this.array[i] = array[i];
        }
        // 设置堆的大小
        this.size = n;
        // 堆化非叶子节点元素
        for (int i = (n-2)/2; i >= 0; i--) {
            heap.percolateDown(i);
        }
    }

    /**
     * 堆排序
     * 
     * 堆排序算法首先将所有元素插入堆中,然后从堆中依次删除根节点元素,直到堆为空
     * @param array 无序数组
     * @return 排序后的数组
     */
    public int[] heapSort(int[] array) {
        // 获取数组大小
        int n = array.length;
        // 创建堆
        Heap heap = new Heap(n, "big");
        // 数组建堆
        heap.buildHeap(heap, array);
        int temp = 0;
        for (int i = 0; i < n; i++) { 
            // 获取根节点元素
            temp = heap.array[0];
            // 将最后一个元素复制到第一个元素位置
            heap.array[0] = heap.array[heap.size - 1];
            // 堆的大小减小
            heap.size--;
            /* 堆化根节点元素,即数组第一个位置的元素 */
            heap.percolateDown(0);
            // 存储删除的元素
            array[i] = temp;
        }
        return array;
    }

    /**
     * 内部方法:堆扩容
     */
    private void resizeHeap() {
        // 创建新的数组,大小为原来数组的两倍
        int[] newArray = new int[2 * capacity];
        // 复制原数组到新数组
        System.arraycopy(this.array, 0, newArray, 0, this.size);
        // 重置数组容量
        capacity = capacity * 2;
        // 复制给原数组,也就是使array指向新生成内存
        array = newArray;
    }

    getter/setter......
}