在算法的总结过程中，主要是快速排序算法，发现了堆排序，然后之前对堆的概念也不是非常清楚，所以这里做一个总结，帮助自己快速上手来辅助算法的学习。2017.7.15，在总结的过程中用到了以下几个博客的知识，在此感谢：CSDN的http://blog.csdn.net/wypblog/article/details/8076324和博客园的http://www.cnblogs.com/JVxie/p/4859889.html

堆的定义

最大（最小）堆是一棵每一个节点的键值都不小于（大于）其孩子（如果存在）的键值的树。大顶堆是一棵完全二叉树，同时也是一棵最大树。小顶堆是一棵完全完全二叉树，同时也是一棵最小树。

完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

注意：
1，堆中任一子树亦是堆。
2，以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。

下图分别给出几个最大堆（大根堆）和最小堆（小根堆）的例子：
最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。
最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。

一些基本术语

A用于表示堆的数组，下标从1开始，一直到n
parent(t)：节点t的父节点，即floor(t/2)
leftchild(t)：节点t的左孩子节点，即:2*t
rightchild(t)：节点t的右孩子节点，即:2*t+1
heapsize(A)：堆A当前的元素数目

需要了解的二叉树信息

深度h为该层的元素（根节点）t的log2(t),例如第0层就是log2(1)=0.
数组放入完全二叉树的时候遵循以上下标格式，例如
下标从1到9分别加入：{8，5，2，10，3，7，1，4，6}。

但此时的完全二叉树并不是一个堆　

堆的基本操作

堆支持以下的基本操作:

•build: 建立一个空堆；
•insert: 向堆中插入一个新元素；
•update：将新元素提升使其符合堆的性质；
•get：获取当前堆顶元素的值；
•delete：删除堆顶元素；
•heapify：使删除堆顶元素的堆再次成为堆。

某些堆实现还支持其他的一些操作，如斐波那契堆支持检查一个堆中是否存在某个元素。

堆的应用

堆排序

堆最常见的应用是堆排序，时间复杂度为O(N lg N)。如果是从小到大排序，用大顶堆；从大到小排序，用小顶堆。
在进行堆排序之前，首先要创建一个堆：该操作主要是将数组A转化成一个大顶堆。思想是，先找到堆的最后一个非叶子节点（即为第n/2个节点），然后从该节点开始，从后往前逐个调整每个子树，使之称为堆，最终整个数组便是一个堆。创建过程如下：

public void buildheap(int[] array, int heapsize) { // 建堆函数
    for (int i = heapsize / 2; i >= 1; i--) {
            heapify(array, i, heapsize);
        }
    }
public void heapify(int[] array, int i, int heapsize) {    // 堆调整函数(这里使用的是最大堆)，也就是根是大于左右子树的
        int leftchild = 2 * i + 1; // 左孩子索引
        int rightchild = 2 * i + 2; // 右孩子索引
        int largest = 0; // 选出当前结点与左右孩子之中的最大值
        if (leftchild < heapsize && array[leftchild] > array[i]) { // 当前节点的左孩子比当前节点大
            largest = leftchild;
        } else
            largest = i;
        if (rightchild < heapsize && array[rightchild] > array[largest]) {
            largest = rightchild;
        } // 以上的两个if判断出三者之中最大的，没有管谁是第二大的
        if(largest!=i){
            exchange(array, i, largest); // 把当前结点和它的最大(直接)子节点进行交换
            heapify(array,largest,heapsize);//注意这里的递归操作是以防
        }
    }


创建好一个大顶！大顶堆后要开始进行交换，每次将堆顶和最后一个换了，换了之后数组剩下的继续重现建堆。接着重复以上的步骤

public void heapsort(int[] array, int heapsize) {
        buildheap(array, heapsize); // 建好了堆（大顶堆）
        for (int i = heapsize; i >= 2; i--) {
            exchange(array, 1, i); // 将堆顶元素(当前最大值)与堆的最后一个元素互换(该操作很有可能把后面元素的稳定性打乱,所以堆排序是不稳定的排序算法)
            heapsize--; // 从堆中去掉最后一个元素
            heapify(array, 1, heapsize); // 从新的堆顶元素开始进行堆调整
        }
    }


完整的代码如下

package 比较排序;

public class HeapSort {

    public static void main(String[] args) {
        int[] array = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大堆排序
        int len = array.length;
        int heapsize = len; // 堆的大小也就是数组长度
        new HeapSort().heapsort(array, heapsize);
        System.out.println("堆排序结果：");
        for (int i = 0; i < len; i++) {
            System.out.print(array[i]);
        }

    }

    public void heapsort(int[] array, int heapsize) {
        buildheap(array, heapsize); // 建好了堆（大顶堆）
        // ================================================
        for (int i = 0; i < heapsize; i++) {
            System.out.print(array[i]);
        }// 测试点，打印堆：
            // ====================================================
        for (int i = heapsize; i > 1; i--) { // 堆顶和堆底互换，堆顶的索引是1，但是对应数组array[0]
            exchange(array, 0, i - 1); // 将堆顶元素(当前最大值)与堆的最后一个元素互换(该操作很有可能把后面元素的稳定性打乱,所以堆排序是不稳定的排序算法)
            heapsize--; // 从堆中去掉最后一个元素
            heapify(array, 0, heapsize); // 从新的堆顶元素开始进行堆调整，
        }
    }

    public void buildheap(int[] array, int heapsize) { // 建堆函数

        for (int i = heapsize / 2; i >= 1; i--) { // 注意，这里的i用的是堆的标号方式，从1开始。但在堆里的索引1对应数组array[0]，所以传入的为i-1
            heapify(array, i - 1, heapsize);
        }
    }

    public void exchange(int[] array, int i, int j) // 交换A[i]和A[j]
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public void heapify(int[] array, int i, int heapsize) { // 堆调整函数(这里使用的是最大堆)，也就是根是大于左右子树的
        int leftchild = 2 * i + 1; // 左孩子索引
        int rightchild = 2 * i + 2; // 右孩子索引
        int largest = 0; // 选出当前结点与左右孩子之中的最大值
        if (leftchild < heapsize && array[leftchild] > array[i]) { // 当前节点的左孩子比当前节点大
            largest = leftchild;
        } else
            largest = i;
        if (rightchild < heapsize && array[rightchild] > array[largest]) {
            largest = rightchild;
        } // 以上的两个if判断出三者之中最大的，没有管谁是第二大的
        if (largest != i) {
            exchange(array, i, largest); // 把当前结点和它的最大(直接)子节点进行交换
            heapify(array, largest, heapsize);
        }
    }
}