数据结构（9）树形结构——大顶堆、小顶堆

待我称王封你为后i 2023-09-23 17:27 75阅读 0赞

**目录**

9.1.概述

9.2.操作

9.2.1.插入

9.2.2.删除

9.2.3.代码实现

--------------------

## 9.1.概述 ##

**概念：**

根节点是自己所在子树中的**最值**的**完全二叉树。**

根节点是所在子树的最大值，称为大顶堆。

根节点是所在子树的最小值，称为小顶堆。

堆的任何子树的根节点到子树上的任意节点，路径上的节点都是有序的，大顶堆为降序，小顶堆为升序。

此处展示一个大顶堆：

![bcc17e16db1c47df8395ab5fb9c71d7f.jpeg][]

**作用：**

堆一般用来在大量数据中找到前N大或者前N小的数据。

**存储：**

一般用数组来存储堆，首先因为堆一般是从空树开始建立的，不论如何操作其一定会是一颗完全二叉树，不存在大量非叶子结点没有左右孩子的情况，所以用数组来表示不会造成内存浪费。其次堆的删除操作需要从叶节点反向向根结点方向遍历，链表结构不太好支持这种反向遍历。

## 9.2.操作 ##

### 9.2.1.插入 ###

堆的插入采用尾插法，新入堆的节点挂在最后一个叶节点上，然后往上浮（交换位置）。

假设已有一颗树，是按照44、25、31、18、10的插入顺序建树的。

假设插入的是20：

![1e670627a2134652aa3ec60918e4fb0d.jpeg][]

假设插入的是35：

![b5ba353e7a6c4ad083cf25cc6a1d40bc.png][]

### 9.2.2.删除 ###

堆的删除操作，从叶子结点开始删除的话，直接删除即可，不会有任何影响，只有在删除非叶子结点时才要考虑进行结点间的调整，保持堆是大顶堆或者小顶堆。

堆在使用时每次弹出的都是堆顶的数据，因此删除操作都是针对堆顶元素的，此处以大顶堆的删除操作为例：

用最末尾的叶节点替换根节点，然后新的根节点与左右孩子比较是否为最大值，若不为最大值，则与参与比较的三个节点中的最大值互换位置，然后递归以上过程，出口为到达叶节点或者到达合适位置。

### 9.2.3.代码实现 ###

package linearStructure.tree.heap;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class MaxTopHeap {
        //存储堆的数组
        private int[] heap;
        //堆的最大存储容量
        private int maxSize;
        //当前堆的存储数量
        private int heapSize;
        public MaxTopHeap(int maxSize) {
            this.heap = new int[maxSize];
            this.maxSize = maxSize;
            this.heapSize = 0;
        }
        // 判断是否为空的方法
        public boolean isEmpty() {
            return heapSize == 0;
        }
    
        // 判断是否填满
        public boolean isFull() {
            return heapSize == maxSize;
        }
    
        // 获取堆顶的值
        public int peek() throws Exception {
            if (heapSize == 0) {
                throw new Exception("heap is empty");
            }
            return heap[0];
        }
    
        // 往堆中添加值
        public void insert (int value) throws Exception {
            if (heapSize == maxSize) {
                throw new Exception("head is full");
            }
            heap[heapSize] = value;
            heapSize++;
            buildMaxHeap(heap);
        }
    
        // 删除堆顶值
        public int poll() throws Exception {
            if (heapSize == 0) {
                throw new Exception("heap is empty");
            }
            int ans = heap[0];
            swap(heap,0,--heapSize);
            buildMaxHeap(heap);
            return ans;
        }
    
        // 建大顶堆
        private int[] buildMaxHeap(int[] array) {
            for (int i = (heapSize-2)/2; i >= 0; i--) {
                adjustDownToUp(array,i,heapSize);
            }
            return array;
        }
    
        private void adjustDownToUp(int[] array, int index, int length) {
            int temp = array[index];
            for (int i = 2*index+1; i < length; i = 2*i+1) {
                if (i < length-1 && array[i] < array[i+1]) {
                    i++;
                }
                if (temp >= array[i]) {
                    break;
                } else {
                    array[index] = array[i];
                    index = i;
                }
            }
            array[index] = temp;
        }
        // 交换元素值
        private void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        // 获取所有元素
        public List<Integer> getAllElements() {
            List<Integer> ans = new ArrayList<>();
            for (int i = 0; i < heapSize; i++) {
                ans.add(heap[i]);
            }
            return ans;
        }
    }

[bcc17e16db1c47df8395ab5fb9c71d7f.jpeg]: https://img-blog.csdnimg.cn/bcc17e16db1c47df8395ab5fb9c71d7f.jpeg
[1e670627a2134652aa3ec60918e4fb0d.jpeg]: https://img-blog.csdnimg.cn/1e670627a2134652aa3ec60918e4fb0d.jpeg
[b5ba353e7a6c4ad083cf25cc6a1d40bc.png]: https://img-blog.csdnimg.cn/b5ba353e7a6c4ad083cf25cc6a1d40bc.png