经典数据结构——堆的实现

叁歲伎倆 2023-01-21 11:22 168阅读 0赞

# 一、完全二叉树 #

堆是一种完全二叉树，什么是完全二叉树？

简单的说，一棵满二叉树表示的是所有节点全部饱和，最后一层全部占满：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70][]

而完全二叉树指的是满二叉树的最后一层，所有叶子节点都从左往顺序排满：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70 1][]

完全二叉树的特点非常简单，**除了最后一层，其他各层节点都是满的，而最后一层，所有节点从左往右依次排满**。它并不关心节点元素的大小，只与这一结构特点有关。

# 二、堆结构 #

前面说到，堆是一种特殊的完全二叉树，除了符合完全二叉树的结构特点，它还有另一个特性，由这个特性，我们又可以将堆分为——**大根堆、小根堆**。

大根堆：每个节点比它的子节都要大。

小根堆：和大根堆相反，每个节点比它的子节点都要小。

> **注意**，堆只关心父节点与子节点之间的大小，要么父节点比子节点都大，视为大根堆；要么父节点比子节点都小，视为小根堆。只要保证这一点，再加上完全二叉树的特点，就是一个堆结构。至于全部节点是否呈现一种左大右小或左小右大的关系，堆并不关心。

如何实现一个堆？

堆并不是一个实际存在的物理结构，它需要通过一个一维数组来表示。实际上，数组表示了堆的一种对应关系。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70 2][]

有了这样一种对应关系，我们可以得到下面 3 个公式：

> 已知任意位置 index，求其父节点和子节点位置：
> 
> 父节点：int fatherIdx = (index - 1) / 2; // 注意， (0 - 1) / 2 = 0，实际上double->int 是向0取整，或绝对值向下取整。
> 
> 左子节点：int leftIdx = index \* 2 + 1;
> 
> 右子节点：int rightIdx = index \* 2 + 2;

例如，4 位置的父节点是 1 位置，(4 - 1) / 2 = 1 ，**向下取整**。

有了位置关系，剩下的工作就是实现大根堆或小根堆，一般情况，大根堆可以快速返回整个堆中的最大值，比较常用，以下就以大根堆为例。

接下来，我们通过代码来详细解析如何实现一个堆结构。

# 三、堆结构的实现 #

以数组为基础，构建一个大根堆的对应关系。这个堆结构需要实现以下几个公共方法：

> 1.  push 入堆
> 2.  pop 出堆
> 3.  isEmpty 是否为空
> 4.  isFull 是否已满

实现堆结构的过程要始终紧扣两个特点：

> 1.  完全二叉树的特点
> 2.  大根堆的特点

只有这两点满足，它才是一个正确的堆。

当push一个元素的时候，由于实现结构是数组，因此始终是追加到数组的末尾，但我们可以通过特定的方法来实现“堆结构”的调整。

想象这个元素被追加到了堆结构最后一层的末尾，首先完全二叉树的条件就满足了。

但是大根堆的特点呢？这时就需要**从末尾开始，向上与父节点比大小，大的站在父节点的位置，然后重复这个过程，直到这个元素不再比父节点大，或已经站在了 0 的位置。**

public void push(int value) {
            if (isFull())
                throw new RuntimeException("heap is full");
            heap[heapSize] = value;
            heapInsert(heap, heapSize++);
        }
       
        private void heapInsert(int[] arr, int index) {
            // 当前位置元素比父节点大，交换位置，重置当前位置
            // 循环条件有两点作用：1、当前节点>父节点（明显）
            // 2、由于 (0-1)/2=0，如果index已经是0位置，出现相等的情况，跳出循环（隐藏）
            while (arr[index] > arr[(index - 1) / 2]) {
                SortUtil.swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

而如果 pop 一个元素，稍微复杂一些，首先，我们需要记录下 0 位置上的元素，然后用堆的最后一个元素补位，heapSize 缩减 1 位，这几步操作是为了保证取出元素后依然是一个完全二叉树。

然后我们需要从 0 位置上（已经替换为最后一个位置上的数）与子节点比较，找到最大的子节点，然后与其交换（下沉），**循环****直到下沉到“堆的最后一层”或子节点都比自己小（终止条件）**：

public int pop() {
            int max = heap[0];
            // 1、要拿掉根节点，因为要保证是一个完全二叉树，所以第一步，我们取最后一个元素补位
            SortUtil.swap(heap, 0, heapSize - 1);
            // 2、heapSize缩减一位
            heapSize--;
            // 2、再执行heapify下沉操作，因为补位的元素可能不满足大根的特点，所以要向下比较
            heapify(heap, 0, heapSize);
            return max;
        }
    
        private void heapify(int[] arr, int i, int heapSize) {
            int left = 2 * i + 1;
            // 若左孩子没有越界，证明存在下一级，有可能需要下沉
            while (left < heapSize) {
                // 选出子节点中最大的那个位置
                int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
                largest = arr[largest] > arr[i] ? largest : i;
                if (largest == i)
                    break;
                else {
                    // 执行交换
                    SortUtil.swap(arr, largest, i);
                    i = largest;
                    left = 2 * i + 1;
                }
            }
        }

以下是完整代码：

/**
     * 大根堆
     *
     * @data 2021/5/15 16:46
     */
    public class Code2_MaxHeap {
        /**
         * 堆容器
         */
        private int[] heap;
        /**
         * 元素限制
         */
        private final int limit;
        /**
         * 堆大小
         */
        private int heapSize;
    
        public Code2_MaxHeap(int limit) {
            this.heap = new int[limit];
            this.limit = limit;
            this.heapSize = 0;
        }
    
        public void push(int value) {
            if (isFull())
                throw new RuntimeException("heap is full");
            heap[heapSize] = value;
            heapInsert(heap, heapSize++);
        }
    
        /**
         * 1、因为是数组表示的堆结构，每次插入都是在末尾，因此，index每次都是堆的最后一个值
         * 2、利用堆结构的特点，可以快速求出当前位置的父节点在数组中的下标，即(index - 1)/2
         * 3、比较当前位置与父节点 大小，如果比父大，交换，然后当前位置变为父节点位置
         * 4、重复 2、3，继续向上比较，要么直到没有父节点，那么while的条件会在两数相等时退出，要么不比父节点大，也停止向上比较。
         */
        private void heapInsert(int[] arr, int index) {
            // 当前位置元素比父节点大，交换位置，重置当前位置
            while (arr[index] > arr[(index - 1) / 2]) {
                SortUtil.swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }
    
        public int pop() {
            int max = heap[0];
            // 1、要拿掉根节点，因为要保证是一个完全二叉树，所以第一步，我们取最后一个元素补位
            SortUtil.swap(heap, 0, heapSize - 1);
            // 2、heapSize缩减一位
            heapSize--;
            // 2、再执行heapify下沉操作，因为补位的元素可能不满足大根的特点，所以要向下比较
            heapify(heap, 0, heapSize);
            return max;
        }
    
        private void heapify(int[] arr, int i, int heapSize) {
            int left = 2 * i + 1;
            // 若左孩子没有越界，证明存在下一级，有可能需要下沉
            while (left < heapSize) {
                // 选出子节点中最大的那个位置
                int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
                largest = arr[largest] > arr[i] ? largest : i;
                if (largest == i)
                    break;
                else {
                    // 执行交换
                    SortUtil.swap(arr, largest, i);
                    i = largest;
                    left = 2 * i + 1;
                }
            }
        }
    
        public boolean isEmpty() {
            return heapSize == 0;
        }
    
        public boolean isFull() {
            return heapSize == heap.length;
        }
    
    }

测试代码：

public static void main(String[] args) {
            int value = 1000;
            int limit = 100;
            int testTimes = 1000000;
            for (int i = 0; i < testTimes; i++) {
                int curLimit = (int) (Math.random() * limit) + 1;
                Code2_MaxHeap my = new Code2_MaxHeap(curLimit);
                RightMaxHeap test = new RightMaxHeap(curLimit);
                int curOpTimes = (int) (Math.random() * limit);
                for (int j = 0; j < curOpTimes; j++) {
                    if (my.isEmpty() != test.isEmpty()) {
                        System.out.println("Oops!");
                    }
                    if (my.isFull() != test.isFull()) {
                        System.out.println("Oops!");
                    }
                    if (my.isEmpty()) {
                        int curValue = (int) (Math.random() * value);
                        my.push(curValue);
                        test.push(curValue);
                    } else if (my.isFull()) {
                        if (my.pop() != test.pop()) {
                            System.out.println("Oops!");
                        }
                    } else {
                        if (Math.random() < 0.5) {
                            int curValue = (int) (Math.random() * value);
                            my.push(curValue);
                            test.push(curValue);
                        } else {
                            if (my.pop() != test.pop()) {
                                System.out.println("Oops!");
                            }
                        }
                    }
                }
            }
            System.out.println("finish!");
        }
    
    /**
     * 遍历数组选出一个最大值 pop
     * 用于验证与自定义MaxHeap.pop的值是相等的。
     */
    class RightMaxHeap {
        private int[] arr;
        private final int limit;
        private int size;
    
        public RightMaxHeap(int limit) {
            arr = new int[limit];
            this.limit = limit;
            size = 0;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        public boolean isFull() {
            return size == limit;
        }
    
        public void push(int value) {
            if (size == limit) {
                throw new RuntimeException("heap is full");
            }
            arr[size++] = value;
        }
    
        public int pop() {
            int maxIndex = 0;
            for (int i = 1; i < size; i++) {
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            int ans = arr[maxIndex];
            arr[maxIndex] = arr[--size];
            return ans;
        }
    }

> 如果一个堆的某个位置的数变了，还不知道变大还是变小，如何重新调整堆结构？ 这个位置 i 顺序调用一下 heapinsert 和 heapify 整个堆就会自动整理好。

# 四、优先级队列与堆 #

java.util.PriorityQueue<T>  是一个优先级队列数据结构，它的底层实现就是用堆来完成的。另外，它是**允许添加重复元素**的，这与 TreeMap 不允许添加重复元素有区别。

这种结构可以立刻返回最大值或最小值，指定一个比较器（参考《[比较器的使用][Link 1]》），符合“正减升，反减降”的口诀。如果是按升序设定比较器，那么 peek 或 poll 方法就会返回最小值。反之就是最大值。

public static void main(String[] args) {
            // 小根堆
            PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o1 - o2);
            heap.add(5);
            heap.add(5);
            heap.add(5);
            heap.add(3);
            //  5 , 3
            System.out.println(heap.peek());
            heap.add(7);
            heap.add(0);
            heap.add(7);
            heap.add(0);
            heap.add(7);
            heap.add(0);
            System.out.println(heap.peek());
            while (!heap.isEmpty()) {
                System.out.println(heap.poll());
            }
        }

# 五、堆的时间复杂度 #

堆结构的时间复杂度主要是看 heapInsert 和 heapify 两个方法。

它们的操作始终与树的高度紧密相关，每次只有一个节点调换，整体是复杂度都是 O(logN)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70]: /images/20221020/ed70025dbc3c425c9b5554f8ce10a959.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70 1]: /images/20221020/76b8db510cec460b94d5e11e40c7a5fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70 2]: /images/20221020/13e0aeb7957c42c4906f60e192c3eed5.png
[Link 1]: https://blog.csdn.net/u014745069/article/details/116853499?spm=1001.2014.3001.5501