8.1、定义

• 堆是计算机科学中一类特殊的数据结构的统称，堆通常可以被看做是一棵 完全二叉树 的 数组对象

• 堆的特性（以大顶堆为例）

  1. 是特殊的 完全二叉树

     除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的， 那么要求 左满右不满
     特殊之处：
     结点大于等于它的两个子结点；右子结点也不比它大

  

  2. 通常用 数组 来实现

     具体方法就是将二叉树的结点按照 层级顺序 放入数组中， 根结点在 位置1（数组索引0处不存储数据），它的子结点在位置2和3，而子结点的子结点则分别在位置4,5,6和7，以此类推

     

     • 如果一个结点的位置为 k，则它的父结点的位置为 k/2

     • 两个子结点的位置则分别为 2k 和 2k+1

       这样，在不使用指针的情况下，也可以通过计算数组的索引在树中上下移动：

       从 a[k] 向上一层，就令k等于 k/2

       向下一层就令k等于 2k 或 2k+1

  3. 每个结点都 大于等于 它的两个子结点

     这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，跟我们之前学习的二叉查找树是有区别的；可以左子结点大于右子结点

     区别于普通的二叉树：
     一般二叉树中右子结点大于父结点

8.2、API

8.3、实现

1）Insert

堆是用 数组 完成数据元素的存储的，由于数组的底层是一串连续的内存地址，所以要往堆中插入数据，只能往数组中从索引0处开始，依次往后存放数据，但是堆中对元素的顺序是有要求的，每一个结点的数据要 大于等于它的两个子结点的数据，所以每次插入一个元素，都会使得堆中的数据顺序变乱，这个时候就需要通过一些方法，让刚才插入的这个数据放入到合适的位置

所以，如果往堆中新插入元素，只需要不断的比较新结点 a[k] 和它的父结点 a[k/2] 的大小，然后根据结果完成数据元素的交换，就可以完成堆的有序调整。

2）delMax

由堆的特性可以知道，索引1处的元素，也就是根结点就 是最大的元素，把根结点的元素删除后，需要有一个新的根结点出现，这时可以 暂时把堆中最后一个元素放到索引1处，充当根结点，但是它有可能不满足堆的有序性需求，这个时候就需要通过一些方法，让这个新的根结点放入到合适的位置

所以，当删除掉最大元素后，只需要将最后一个元素放到索引1处，并不断的拿着当前结点 a[k] 与它的子结点a[2k] 和 a[2k+1] 中的较大者交换位置，即可完成堆的有序调整。

3）代码

package chapter06;

/**
 * @author 土味儿
 * Date 2021/9/8
 * @version 1.0
 * 堆
 */
public class Heap<T extends Comparable<T>> {
    /**
     * 存储元素的数组
     */
    private T[] items;
    /**
     * 元素个数
     */
    private int n;

    /**
     * 构造器
     *
     * @param capacity
     */
    public Heap(int capacity) {
        //this.items = (T[]) new Object[capacity+1];
        this.items = (T[]) new Comparable[capacity+1];
        this.n = 0;
    }

    /**
     * 插入元素t
     *
     * @param t
     */
    public void insert(T t) {
        // 在结尾插入
        items[++n] = t;
        // 让新元素上浮，找到合适的位置
        swim(n);
    }

    /**
     * 删除最大元素并返回
     *
     * @return
     */
    public T delMax() {
        // 最大元素
        T max = items[1];

        // 交换索引1处 和 最大索引处的元素，让完全二叉树中最右的元素成为临时根结点
        exch(1, n);

        // 删除交换后最大索引处的元素，即原根结点（最大元素）
        items[n] = null;

        // 元素数量减1
        n--;

        // 让新根结点下沉，找到合适位置
        sink(1);

        return max;
    }

    /**
     * 判断索引i处的元素是否比j处的小
     *
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    /**
     * 交换索引i处与j处的元素
     *
     * @param i
     * @param j
     */
    private void exch(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    /**
     * 上浮
     * 使索引k处的元素处于适当的位置
     *
     * @param k
     */
    private void swim(int k) {
        // 循环比较索引k处元素和它父结点元素，如果父结点小，就交换位置
        while (k > 1) {
            // 比较当前结点与父结点
            if (less(k / 2, k)) {
                // 父比子小，交换位置
                exch(k / 2, k);
            }
            k = k / 2;
        }
    }

    /**
     * 下沉
     * 使索引k处的元素处于适当的位置
     *
     * @param k
     */
    private void sink(int k) {
        // 循环比较当前结点k 和 max(左子结点2k，右子结点2k+1)的值，如果当前结点k小，就交换位置

        // 循环条件 2*k <= n ：表示存在左子结点
        while (2 * k <= n) {
            // 获取当前结点中的较大子结点

            // 记录较大子结点索引：默认为左子结点
            int max = 2 * k;
            // 右结点存在，且左小于右，改变max
            if (2 * k + 1 <= n && less(2 * k, 2 * k + 1)) {
                max = 2 * k + 1;
            }

            if (!less(k, max)) {
                // 当前结点不小于子结点，退出循环
                break;
            }

            // 当前结点小于子结点，交换位置
            exch(k, max);

            // 交换k值，继续循环
            k = max;
        }
    }
}

public class HeapTest {
    @Test
    public void test() {
        Heap<String> heap = new Heap<String>(20);

        heap.insert("A");
        heap.insert("B");
        heap.insert("C");
        heap.insert("D");
        heap.insert("E");
        heap.insert("F");
        heap.insert("G");

        String res;
        while ((res = heap.delMax()) != null) {
            System.out.print(res + " ");
        }
    }
}

G F E D C B A 

8.4、堆排序

给定一个数组：
String[] arr = {“S”,“O”,“R”,“T”,“E”,“X”,“A”,“M”,“P”,“L”,“E”}
请对数组中的字符按从小到大排序

• API

• 实现步骤

  1. 构造堆

  2. 得到堆顶元素，这个值就是最大值

  3. 交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经放到合适的位置

  4. 对堆进行调整，重新让除了最后一个元素的剩余元素中的最大值放到堆顶

  5. 重复2~4这个步骤，直到堆中剩一个元素为止

1）堆构造过程

堆的构造，最直观的想法就是另外再创建一个新数组，然后从左往右遍历原数组，每得到一个元素后，添加
到新数组中，并通过上浮，对堆进行调整，最后新的数组就是一个堆

上述的方式虽然很直观，也很简单，但是可以用更聪明一点的办法完成它

• 创建一个新数组，把原数组0 ~ length-1的数据拷贝到新数组的 1 ~ length 处，再从新数组 长度的一半 处开始往 1索引 处扫描（从右往左），然后对扫描到的每一个元素做下沉调整即可

  原数组：待排序的目标数组
  新数组1~length处：新数组是要作为堆的形式存在；在堆中，0索引处不存储数据

  为什么是新数组长度的一半？

  因为新数组是一个无序堆，长度的一半之后的结点为叶子结点；叶子结点不需要要下沉调整

  证明：设长度为n

  ---

  假如 长度一半(n/2) 的 下一个结点(n/2)+1 有子结点

  那么它的子结点为：2 * [(n/2)+1] = n+2 或 2 * [(n/2)+1]+1 = n+3

  可以看到子结点的索引已超出长度n，所以假设不成立，即长度一半的下个结点没有子结点，是叶子

  ---

  长度一半(n/2)，它的叶子为：2 * (n/2) = n，等于数组长度；后面的结点若再有子结点，就超出长度n

2）堆排序过程

对构造好的堆，只需要做 类似于堆的删除操作，就可以完成排序：

1. 将堆顶元素和堆中最后一个元素交换位置

2. 通过对堆顶元素下沉调整堆，把最大的元素放到堆顶 (此时最后一个元素不参与堆的调整，因为最大的数据已经到了数组的最右边)

3. 重复1~2步骤，直到堆中剩最后一个元素

3）代码测试

package chapter06;

/**
 * @author 土味儿
 * Date 2021/9/8
 * @version 1.0
 * 堆排序
 */
public class HeapSort<T extends Comparable<T>> {
    /**
     * 对source数组从小到大排序
     *
     * @param source
     */
    public static void sort(Comparable[] source) {
        // 构建堆
        Comparable[] heap = new Comparable[source.length + 1];
        createHeap(source, heap);

        // 定义一个变量n，记录未排序的元素中的最大索引
        int n = heap.length - 1;

        // 循环遍历
        while (n > 1) {
            // 交换 索引1处的元素 和 未排序元素中最大索引处的元素
            exch(heap, 1, n);

            // 更新未排序元素中的最大索引n
            n--;

            // 对索引1处的新元素作下沉调整
            sink(heap, 1, n);
        }

        // 至此heap已经有序；拷贝到原数组中
        System.arraycopy(heap,1,source,0,source.length);
    }

    /**
     * 由原数组source，构造出heap
     *
     * @param source
     * @param heap
     */
    private static void createHeap(Comparable[] source, Comparable[] heap) {
        // 把source中元素拷贝到heap中，heap就形成一个无序堆
        System.arraycopy(source, 0, heap, 1, source.length);

        /*
        对heap中的元素作下沉调整：从长度的一半开始，从右向左，向索引1处(根结点)扫描
        依次对每一个结点做下沉调整
        调整完之后成为一个真正的堆：每个结点都大于等于它的子结点
         */
        for (int i = (heap.length) / 2; i > 0; i--) {
            sink(heap, i, heap.length - 1);
        }

    }

    /**
     * 判断heap中索引i处元素是否小于索引j处的元素
     *
     * @param heap
     * @param i
     * @param j
     * @return
     */
    private static boolean less(Comparable[] heap, int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }

    /**
     * 交换heap中索引i处和j处元素
     *
     * @param heap
     * @param i
     * @param j
     */
    private static void exch(Comparable[] heap, int i, int j) {
        Comparable temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    /**
     * heap中索引target处的元素下沉，范围为 0 ~ range
     *
     * @param heap
     * @param target
     * @param range
     */
    private static void sink(Comparable[] heap, int target, int range) {
        // 循环比较当前结点target 和 max(左子结点2target，右子结点2target+1)的值，如果当前结点target小，就交换位置

        // 循环条件 2*target <= range ：表示存在 左子结点
        while (2 * target <= range) {
            // 获取当前结点中的 较大子结点

            // 记录较大 子结点索引：默认为 左子结点
            int max = 2 * target;
            // 如果右结点存在，且左小于右，改变max
            if (2 * target + 1 <= range && less(heap, 2 * target, 2 * target + 1)) {
                max = 2 * target + 1;
            }

            if (!less(heap, target, max)) {
                // 当前结点不小于子结点，退出循环
                break;
            }

            // 当前结点小于子结点，交换位置
            exch(heap, target, max);

            // 更新k值，继续循环
            target = max;
        }
    }
}

    @Test
    public void testHeapSort() {
        // 待排序数组
        String[] arr = {"S","O","R","T","E","X","A","M","P","L","E"};

        // 通过HeapSort排序
        HeapSort.sort(arr);

        // 输出
        System.out.println(Arrays.toString(arr));

    }

[A, E, E, L, R, M, O, P, S, T, X]

4）性能测试

@Test
    public void testHeapSort() {
        // 从大到小
        Integer[] c = getArray(100_0000);
        // 从小到大
        //Integer[] c = getArray1(100_0000); 
        // 随机
        //Integer[] c = getArray2(100_0000);
        System.out.println("未排序前首元素：" + c[0]);
        long start = System.currentTimeMillis();
        HeapSort.sort(c);
        long end = System.currentTimeMillis();
        System.out.println("用时：" + (end - start));
        System.out.println("排序后首元素：" + c[0]);

    }

    /**
     * 得到待排序数组
     * 最坏情况（倒序，从大到小）
     *
     * @param n
     * @return
     */
    private Integer[] getArray(int n) {
        Integer[] c = new Integer[n];
        for (int i = 0; i < n; i++) {
            c[i] = n - i;
        }
        return c;
    }

	/**
     * 得到待排序数组
     * 从小到大
     *
     * @param n
     * @return
     */
    private Integer[] getArray1(int n) {
        Integer[] c = new Integer[n];
        for (int i = 0; i < n; i++) {
            c[i] = i+1;
        }
        return c;
    }

    /**
     * 得到待排序数组
     * 随机
     *
     * @param n
     * @return
     */
    private Integer[] getArray2(int n) {
        Integer[] c = new Integer[n];
        Random r = new Random();
        for (int i = 0; i < n; i++) {
            c[i] = r.nextInt(n);
        }
        return c;
    }

// 原数组从大到小
未排序前首元素：1000000
用时：35
排序后首元素：1  
  
// 原数组从小到大    
未排序前首元素：1
用时：70
排序后首元素：1    
    
// 原数组随机
未排序前首元素：627529
用时：58
排序后首元素：1

待排序数组：倒序100_0000条 （100_0000 ~ 1)

排序方法	用时(毫秒)
堆排序	70
希尔排序	120
归并排序	119
快速排序	栈溢出