堆&堆排序

堆的定义

堆是一个完全二叉树
除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值
堆中每个节点的值都大于等于(或者小于等于)其左右子节点的值。

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

大顶堆：每个节点的值都大于等于子树中每个节点值。
小顶堆：每个节点的值都小于等于子树中每个节点值。

堆的存储

完全二叉树适合用数组存储。节省存储空间，不需要存储左右节点的指针，单纯的通过数组下标就可以找到节点的左右节点和父节点。

假设堆中的数据从数组下标为1的位置开始存储。
数组中下标为i的节点的左子节点就是下标为i2的节点，右子节点就是下标为i2+1的节点，父节点就是下标为i/2的节点。

堆的操作

往堆中插入一个元素或者删除堆顶元素后，数据结构不满足堆的特性，对其进行调整让它重新满足堆的特性，该过程称为堆化。
堆化分为从下往上和从上往下两种。顺着节点所在路径，对比然后交换。

插入一个元素-从下往上堆化。
将节点放在数组最后，然后让新插入的节点与父节点对比大小。如果不满足自己点小于等于父节点的大小关系，就互换两个节点。一直重复这个过程，直到父子节点之间满足大小关系。

插入

public class Heap {
    //数组，从下标1开始存储数据
    private int[] a;
    //堆可以存储的最大数据个数
    private int n;
    //堆中已经存储的数据个数
    private int count;

    public Heap(int capacity) {
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
    }

    public void insert(int data) {
        //堆满
        if(count >= n) return;
        count++;
        a[count] = data;
        int i = count;
        //自下往上堆化
        while(i/2 > 0 && a[i] > a[i/2]) {
            //交换下标为i和i/2的两个元素
            swap(a,i,i/2);
            i = i/2;
        }
    }
}

删除堆顶元素-从上往下堆化。
堆顶元素存储的是堆中数据的最大值或者最小值。

方法1：当删除堆顶元素之后，把第二大元素放到堆顶，第二大元素必然是左右子节点之一。迭代删除第二大节点，以此类推直到叶子节点被删除。最后堆化出来的堆不满足完全二叉树特性，可能出现空洞。

方法2：当删除堆顶元素之后，把最后一个元素放到堆顶，然后利用父子节点对比方法，对不满足父子节点大小关系的交换两个节点，重复这个过程，直到父子节点之间满足大小关系为止。移除的是数组最后一个元素，堆化过程中都是交换操作，不会出现数组空洞，满足完全二叉树特性。

删除

public class Heap {
    //数组，从下标1开始存储数据
    private int[] a;
    //堆可以存储的最大数据个数
    private int n;
    //堆中已经存储的数据个数
    private int count;

    public Heap(int capacity) {
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
    }

    public void removeMax() {
        //堆中没有数据
        if(count == 0) return -1;
        a[1] = a[count];
        count--;
        heapify(a,count,1);
    }
    //自上往下堆化
    private void heapify(int[] a,int n,int i) {
        while（true) {
            int maxPos = i;
            if(i*2 <= n && a[i] < a[i*2])
                maxPos = i*2;
            if(i*2+1 <= n && a[maxPos] < a[i*2+1])
                maxPos = i*2+1;
            if(maxPos == i)
                break;

            swap(a,i,maxPos);
            i = maxPos;    
        }

    }
}

包含n个节点的完全二叉树，树的高度不会超过log₂n。堆化的过程是顺着节点所在路径比较交换的，堆化的时间复杂度跟树的高度成正比，为O(logn)。插入数据和删除堆顶元素的的主要逻辑是堆化，所以往堆中插入一个元素和删除堆顶元素的时间复杂度都是O(logn)。

堆排序

借助堆这种数据结构实现的排序算法称为堆排序。时间复杂度为O(nlogn),原地不稳定排序算法。
堆排序的过程分为两个步骤：建堆、排序。

建堆
不借助另一个数组，在原数组上操作建堆。

从前往后处理数组数据，从下往上堆化。

在堆中插入一个元素的思路。数组中包含n个数据，假设起初堆中只包含一个数据，就是下标为1的数据。然后调用插入操作，将下标从2到n的数据依次插入到堆中最后一个位置，并进行堆化，不符合大小关系就交换位置，重复，最后将包含n个数据的数组组织成了堆。
从后往前梳理数据，每个数据都是从上往下堆化。

从最后一个非叶子节点开始倒序依次堆化，不符合大小关系就交换位置。叶子节点往下堆化只能自己跟自己比较。

建堆

private static void buildHeap(int[] a,int n) {
    for(int i = n/2; i >= 1; i--) {
        heapify(a,n,i);
    }
}
private static void heapify(int[] a,int n,int i) {
    while（true) {
         int maxPos = i;
         if(i*2 <= n && a[i] < a[i*2])
             maxPos = i*2;
         if(i*2+1 <= n && a[maxPos] < a[i*2+1])
             maxPos = i*2+1;
         if(maxPos == i)
             break;

         swap(a,i,maxPos);
         i = maxPos;    
     }
}

完全二叉树下标n/2 + 1到n的节点是叶子节点不需要堆化，只需对下标从n/2到1的数据进行堆化。
每个节点的堆化的时间复杂度是O(logn)，n/2 + 1个节点堆化的总时间复杂度就是O(nlogn)。(粗略)

叶子节点不需要堆化，需要堆化的的节点从倒数第二层开始，每个节点堆化的过程中，需要比较和交换的节点个数跟这个节点的高度k成正比，将每个节点的高度求和得到建堆的时间复杂度：

S=1h + 2¹(h-1) + 2²(h-2) +
2^k(h-k) + 2^h-1*1

公式左右乘以2，再错位对齐后与原公式相减，中间是个等比数列

= -h + 2 + 2² + 2³ + ··· + 2^k + ··· + 2^h-1 + 2^h
= -h + (2^h-2) + 2^h
= 2^h+1 -h -2

h=log₂n,S=O(n).

建堆的时间复杂度为O(n)。

排序
建堆结束后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也是最大的元素。
将堆顶元素与最后一个元素交换，最大元素就放到了下标为n的位置。类似删除堆顶元素操作。堆顶元素被移除，下标为n的最小元素被放到堆顶，通过堆化的方法将剩下的n-1个元素重新构建成堆；再取堆顶元素(原堆第二大元素)-与n-1位置的元素交换-堆化-重复。直到最后堆中只剩下下标为1的一个元素，排序完成。

排序

//n表示数据的个数，数组a中的数据从下标1到n的位置
public static void sort(int[] a,int n) {
    buildHeap(a,n);
    int k = n;
    while(k>1) {
        //当前堆尾与堆顶交换
        swap(a,1,k);
        k--;
        //只需要堆化堆顶元素
        heapify(a,k,1);
    }
}

整个堆排序的过程，只需要极个别的临时存储空间，属于原地排序算法。
堆排序包括建堆和排序两个操作，建堆的时间复杂度是O(n)，排序过程的时间复杂度是O(nlogn)，堆排序整体的时间复杂度是O(nlogn)。
堆排序过程中，将堆的最后一个节点跟堆顶节点互换，改变了值相同数据的原始相对顺序。堆排序不是稳定的排序算法。

对比快排

堆排序数据访问的方式没有快速排序友好。
快排数据是顺序访问的，堆排序堆化过程数据是跳着访问的(2的指数)，对CPU缓存不友好。
同样的数据，在排序过程中，堆排序的数据交换次数多于快速排序。
快排数据交换的次数不会比逆序多。堆排序建堆的过程会打乱数据原有的相对先后顺序，导致原数据有序度降低。

扩展

用数组存储表示完全二叉树时，若从下标为0开始存储，如果节点下标是i，则左子节点的下标就是2i+1，右子节点的下标是2i+2，父节点的下标是(i-1)/2。