堆的创建、插入、删除以及堆排序算法总结

在说堆的概念之前先说一下关于树和二叉树的一点儿知识~~

1. 树

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，叶子朝下的。

1.1 树的特点：

• 每个节点有零或多个子节点
• 没有父节点的节点称为根节点
• 每个非根节点有且仅有一个父节点
• 除了根节点外，每个子节点可以分成多个不相交的子树

1.2 树里面的部分概念：

• 节点的度：一个节点含有的子树的个数称为该节点的度
• 叶节点或终端节点：度为0的节点
• 非终端节点或分支节点：度不为0的节点
• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点
• 兄弟节点：具有相同父节点的节点互称为兄弟节点
• 树的度：一棵树中，最大的节点的度称为树的度
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
• 树的高度或深度：树中节点的最大层次
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟
• 节点的祖先：从根到该节点所经分支上的所有节点
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙
• 森林：由m（m>=0）棵互不相交的树的集合称为森林

1.3 树与非树：

• 树的子树都是不相交的
• 除了根节点外，每个节点有且仅有一个父节点
• 一棵n个节点的树有n-1条边

2. 二叉树

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为“左子树”和“右子树”的二叉树组成。

2.1 二叉树的特点：

• 每个结点最多有两棵子树，即二叉树不存在度大于2的结点
• 二叉树的子树有左右之分，其子树的次序不能颠倒

2.2 特殊的二叉树：

满二叉树：
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1，则它就是满二叉树。

完全二叉树：
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 满二叉树是一种特殊的完全二叉树。

2.3 二叉树的顺序存储结构：

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。

堆就是按照顺序结构存储的一棵二叉树，堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆，即堆中某个节点的值总是不大于或不小于其父节点的值。

堆排序的思路：
要实现从小到大排序则首先要建立一个大根堆！！！
也就是说在堆排序之前需要把二叉树变成一个大根堆！！！
1）调整：从当前二叉树的最后一棵子树开始进行调整；
2）找孩子里面的最大值和父亲进行比较；
3）如果孩子里面的最大值大于父亲，则二者进行交换，否则直接结束（本来就是大根堆）；
4）整个堆是从下往上进行调整，但是每棵子树是向下调整的。

package com.github.jihaojiemo;

import java.util.Arrays;

/**
 * Description: 堆
 * Author: admin
 * Create: 2019-06-04 21:03
 */
public class TestHeap implements IHeap {

    private int[] elem;
    private int usedSize;
    private static final int DEFAULT_SIZE = 10;

    public TestHeap() {
        this.elem = new int[DEFAULT_SIZE];
        this.usedSize = 0;
    }

    //从每棵子树的根节点开始调整，调整的长度为len
    public void AdjustDown(int root, int len) {
        int parent = root;
        int child = 2 * parent + 1;//左孩子

        while (child < len) {
            //找左右孩子最大值
            if (child + 1 < len && elem[child] < elem[child + 1]) {//右孩子大（child+1有可能越界）
                ++child;//child下标存放的是左右孩子的最大值
            }
            //左右孩子最大值跟父节点比较
            if (elem[child] > elem[parent]) {
                //如果左右孩子最大值大于父节点则进行交换
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;

                //parent指向child，child指向左孩子
                //因为不一定只交换一次
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    //初始化建立大根堆
    public void initHeap(int[] array) {
        //先把数组里面的值全部赋给elem
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
        //然后从最后一棵子树父节点（array.length-1-1）开始向下调整
        //子推父：孩子节点 n，父节点 (n-1)/2
        //父推子：父节点 n，左孩子 2n+1，右孩子 2n+2
        for (int i = (array.length - 1 - 1) / 2; i >= 0; i--) {
            AdjustDown(i, this.usedSize);
        }
    }

    //向上调整，从孩子节点开始调整
    public void AdjustUp(int child) {
        int parent = (child - 1) / 2;

        while (child > 0) {
            if (elem[child] > elem[parent]) {
                //如果孩子大于父亲则交换
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;

                //child指向parent，parent向上走
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }

    public boolean isFull() {
        return this.usedSize == this.elem.length;
    }

    //插入item到堆中
    public void pushHeap(int item) {
        if (isFull()) {
            //2倍扩容
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
        }
        this.elem[this.usedSize] = item;
        this.usedSize++;
        //插入之后就不再是大根堆了，向上调整
        AdjustUp(this.usedSize-1);
    }

    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    //删除堆顶元素
    public int popHeap() {
        if (isEmpty()) {
            throw new UnsupportedOperationException("堆为空");
        }
        //堆顶元素和最后一个元素交换
        int oldData = elem[0];
        int temp = elem[0];
        elem[0] = elem[this.usedSize - 1];
        elem[this.usedSize - 1] = temp;

        this.usedSize--;

        //又不是大根堆了，所以要向下调整
        AdjustDown(0, this.usedSize);
        return oldData;
    }

    //返回堆顶元素，不删除数据元素
    public int getHeapTop() {
        if (isEmpty()) {
            throw new UnsupportedOperationException("堆为空");
        }
        return this.elem[0];
    }

    /**
     * 堆排序：
     *   1.时间复杂度：O(nlog2n)
     *   2.空间复杂度：O(n)
     *   3.稳定性：不稳定
     */
    //堆排序
    public void heapSort() {
        int end = this.usedSize-1;//要交换的最后一个下标
        while (end > 0) {
            int temp = elem[0];
            elem[0] = elem[end];
            elem[end] = temp;
            //只需要调整0号下标的树
            AdjustDown(0, end);
            end--;
        }
    }

    //打印堆
    public void show() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
}

package com.github.jihaojiemo;

/**
 * Description:
 * Author: admin
 * Create: 2019-06-11 19:48
 */
public class TestDemo {

    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        testHeap.initHeap(array);
        testHeap.show();

        testHeap.pushHeap(11);
        testHeap.show();

        testHeap.popHeap();
        testHeap.show();

        testHeap.heapSort();
        testHeap.show();
    }
}

这个结果都是我一一验证过的，应该是没什么大问题的，在这里就不再画图进行说明了。

二叉树的链式存储请关注下篇博客！

如有问题，欢迎指正~~