树论-堆树(Heap Tree)（数据结构中树和堆的区别）

堆树（Heap Tree）

Kitten 2023-09-12

前言

堆的定义

堆是一种特殊的树，它需要满足以下几点。

（一）是一颗完全二叉树（除了叶子结点，其它非叶子结点都有左右子树，也就是满的。并且叶子结点都要靠左连续排列）

（二）其中每一个结点的值都大于等于或者小于等于其左右结点的值

根据这个性质，那么对于每一个结点的值都大于等于其左右结点的值我们就称之为大顶堆。

对于每一个结点的值都小于等于其左右结点的值的堆我们就称之为小顶堆。

注：关于树的定义可以看看另一篇文章：数据结构-树论

堆树的存储

在树论中我们都知道树的实现有链表和数组两种方式，在通常情况下数组有更好的性能，所以我们会使用数组作为树的主要实现方式，堆树也不例外。所以堆树也满足：假设任意结点在数组的下标为i，那么它的左右结点分别为：(2 * i ) 和 (2 * i+1)，如果是从0开始存储的话那就是(2 * i +1)和 (2 * i+2)。

堆树的操作

插入结点（堆化）

对于堆插入的操作，我们其实也可以叫做堆化，插入结点有两种实现方式，分别为

（一）从下往上插入

从根结点开始插入，然后依次往下和它的左右子结点做比较交换，直到不能交换为止。

（二）从上往下插入

从最后一个尾结点开始插入，然后依次往上和它的父亲结点做比较交换，直到不能交换为止。

比如我们有如下的堆树，现在要插入结点9，插入后先和7比较，比7大做交换，此时并没有结束，而是要继续和10比较，如果此时是大于10的就要继续和10交换，但是此时是9比10小所有就结束了。所以要注意插入时的退出条件为，直到不能交换为止。

结点的删除

结点的删除为，以被删除的结点和最后一个结点做交换，然后把最后一个结点作为新加入的结点，从上往下做堆化。堆化结束后直接删除此时最后一个结点。其实删除也会涉及堆化。

思考：为什么不能直接删除，因为会造成树不是一颗完全二叉树。

堆排序

建堆

对于一个已经存在的数组A，使用堆排序的话首先就要先创建一个堆结构，我们称之为建堆，那么如何创建堆结构呢？我们可以分两种方式。

（一）从无到有，忽略已存在的结构A，新开一个大小相同的数组，将原数组中的元素依次取出，使用我们刚才提过的从上至下堆化的方法以此将所有元素堆化到一个新的数组中。那么这个方法肯定是可行的。但是这个方法需要新开一个连续数组空间，所以实际哈上肯定不会选择这种方法。

（二）使用一种可以修正原数组的方法解决，

从最后一个非叶子结点堆化

注：为什么从最后一个非叶子结点开始？因为叶子结点没有左右子树，不需要比较，所以需要从倒数第一个非叶子结点开始做堆化才有意义。

比如对于序列：A={8,4,20,7,3,1,25,14,17}

它的倒数第一个非叶子结点就是如右图中黄色结点，也就是7。

那么堆化的过程就是从7开始，向下做堆化。

整体的建堆过程为：

建堆从下往上时间复杂度

堆排序

经过上面建堆过程后，我们得到了一个最大的堆顶元素，此时排序我们只需将堆顶和最后一个结点进行交换，交换后进行一次堆化，依次进行这个操作就可以完成堆的排序。

排序上往下时间复杂度计算

演示动画如下

代码实现

public class HeapTree<T extends Comparable<T>> {

    private final T[] data;

    public HeapTree(T[] data) {
        this.data = data;
    }

    private void heapSort() {
        int len = data.length;

         // 从第一个非叶子节点开始建堆，len / 2 - 1 就是第一个非叶子结点
        for (int i = len / 2 - 1; i >= 0; i--) {
            createHeap(data, i, len);
        }
        //上面步骤结束后会得到一棵堆树

        // 堆排序
        for (int i = len - 1; i > 0; i--) {
            // 如果堆顶大于最后一个结点，则交换
            if (data[0].compareTo(data[i]) > 0) {
                T temp = data[0];
                data[0] = data[i];
                data[i] = temp;
                // 从上往下从堆顶做建堆操作
                createHeap(data, 0, i);
            }
        }
    }

    /**
     * 建堆
     *
     * @param data 原数组
     * @param s    建堆的开始索引
     * @param e    结束建设堆标志索引
     */
    private void createHeap(T[] data, int s, int e) {
        int p = s;
        // 如果数组从0开始存储就+1，如果从1开始不用+1
        int left = (p >> 1) + 1;
        while (left < e) {
            int max = left;
            int right = left + 1;
            // 右子树<小于结束条件 并且 右子树>左子树
            if (right < e && data[left].compareTo(data[right]) < 0) {
                // 右结点和父结点交换
                max = right;
            }
            // 父结点大于左右结点，不交换
            if (data[p].compareTo(data[max]) > 0) {
                return;
            } else {
                // 交换值
                T t = data[p];
                data[p] = data[max];
                data[max] = t;
                p = max;
                left = (p >> 1) + 1;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] data = { 1, 21, 3, 5, 45, 6, 23 };
        HeapTree<Integer> heapTree = new HeapTree<>(data);
        heapTree.heapSort();
        for (int t : heapTree.data) {
            System.out.println(t);
        }
    }
}

堆树的应用场景

我么所熟知的堆树应用场景其实就是指的是堆排序的应用场景，通过我们的计算堆排序的时间复杂度为n+O(nlogn)，而且它是一个不稳定的排序方式，较于快排的O(nlogn)时间复杂度。堆排序并没有什么优势，在排序场景中能选择堆排序方式都可以使用快速排序拼移替换。所以使用堆排序的场景就比较局限了，在很多时候堆排序的另一种叫法叫做优先级队列，也就是说优先级队列的排序方式就是堆排序。因为对于一个优先级队列涉及到结点的出队入堆，也就是堆树的建堆过程。所以堆树其实和优先级队列可以说是基本贴合了。

另外一方面堆排序被广泛得利用于计算TOP K的场景中。