完全二叉堆

堆又可称之为完全二叉堆。这是一个逻辑上基于完全二叉树、物理上一般基于线性数据结构（如数组、向量、链表等）的一种数据结构。

完全二叉树的存储结构

学习过完全二叉树的同学们都应该了解，完全二叉树在物理上可以用线性数据结构进行表示（或者存储），例如数组int a[5] = {1,2,3,4,5}就可以用来描述一个拥有5个结点的完全二叉树。那么基于完全二叉树的堆结构自然也可以使用线性结构进行描述。回顾一下这样表示时，元素的秩之间的关系。若有元素秩为k(k >= 0)，则有Rank(LeftChild) = 2k+1，Rank(RightChild) = 2k+2（此处元素的秩从0开始，若从1开始则推导出的公式略有不同，注意这之间的区别）。

堆的有序性

堆可分为两种：大根堆（最大堆）、小根堆（最小堆）。

大根堆

何为大根堆？顾名思义，大根堆即指在逻辑上的二叉树结构中，根结点>子结点，总是最大的，并且在堆的每一个局部都是如此。例如{3,1,2}可以看作为大根堆，而{3,2,1}亦可以看作为大根堆。大根堆的根结点在整个堆中是最大的元素。

小根堆

小根堆的性质与大根堆类似，只不过在二叉树的结构中，根结点<子结点。例如{1,2,3}为小根堆，{1,3,2}同样也是小根堆。小根堆的根结点在整个堆中是最小的元素。

小结

1. 大/小根堆中根结点即是整个序列中最大 /小的元素，那么从堆中获取最大/小的元素则非常快速，只要返回序列中的首元素即可。
2. 更一般的，堆处处局部的有序性，形成了堆整体的有序性。 只要有一处局部没有满足堆的有序性，则可以说堆失序，此时便需要进行相应的调整。

堆的常用场景

1、根据之前的总结，我们可以利用堆的性质来找出一个序列中最大/小的元素，这不失为一种方法，尽管通过遍历来解决这一问题可能更好。
2、堆排序，相信学习过堆排序的同学对此都会认同。
3、建立优先级队列，根据上述的小结可知，若利用堆来建立优先级队列，可以快速的获取到队列中优先级最高/低的任务。
4、n个元素中排列出前k大的元素问题，对于此类问题，可以建立一个小根堆，依次读入n个元素并调整，并在堆的规模达到k+1时，剔除掉第1个元素，剩下k个较大元素，保持堆的规模不超过k，一直循环即可得到最终的结果。
5、其他的应用还请各路大神留言指导，互相探讨，小弟感激不尽。

堆的操作

堆的操作呢，无非就是建立、插入、删除。建立一个空的堆是非常简单的操作，而利用一个已有的序列生成一个是一个值得思考的问题；插入和删除操作，比较简单；值得思考的是插入元素或者删除元素之后如何恢复堆的堆序性。

堆的插入与上滤

1. 往一个线性序列中插入一个元素是比较简单的，例如数组a[N]，在秩为k(k<N)的位置上插入一个元素e，分为以下操作：a) 将秩大于等于k的元素依次后移一位；b)将a[k]赋值为e。
2. 假设堆使用数组作为底层的实现，那么堆的插入又该如何实现呢？是插入到原堆的头部？还是尾部？亦或是中间？ 鉴于原堆已经保持了堆序性，如果插入在头部，相当于所有元素对应的父结点和子结点都会发生变化，这样一来会导致整个堆失效；如果插入在中间的某一位置，则会导致插入位置之后的所有元素对应的父结点和子结点发生变化，这样一来会导致堆的部分失效；如果插入在堆底，则原堆的结构未遭破坏，此时唯一可能不符合堆性质的只是最后一个元素（刚刚插入的元素）的父结点是否比它大/小，即在这个局部是否还满足之前所说的堆序性。
3. 好，现在，可以确定在堆底插入新元素的代价是最小的，那么接下来就是思考在这种情况下如何恢复堆序性。试想一个小根堆如下{2,3}，在其尾部插入元素1，如何调整使其满足小根堆的性质呢？对，通过将元素2和元素1交换即可得到小根堆{1,3,2}。此时回顾以下小根堆的性质便不难看出，在此种情形下，对失序的堆执行以下操作即可恢复其堆序性：若新插入结点小于其父结点，则将两者交换。
4. 在第三条所阐述的情况中，并没有对新插入结点的兄弟结点（如果有的话）做任何操作，甚至不需要考虑它，这是为何？假设新插入结点为N，其父结点为F(N)，其兄弟结点为B(N)，则在原堆（结点N插入之前）中有这样的关系：F(N) < B(N)。插入结点N后，若N < F(N)，则有N < F(N) < B(N)。回顾堆序性的描述，不难知道只要将N与F(N)互换位置就可以使得堆恢复堆序性。
5. 由点及面，假设上述的堆{2,3}只是另一个堆heap2中的局部（3为heap2中的堆底元素，2为3的父结点），通过上一条阐述的操作，我们可以恢复局部的堆序性，但别忘了，由于原来元素2变成了元素1，此时要继续检查元素1以及元素1的父结点、兄弟结点组成的局部堆是否满足堆序性，循环往复直到插入元素所处的局部满足了堆序性。这样的一个过程也称为堆的上滤（percolateUp）。
   代码如下：

template<typename T>
void  percolateUp(T *s, size_t rank)
{
	while(rank)
	{
		size_t f = (rank-1)>>1;
		if (s[f] > s[rank])
		{
			swap(s[f], s[rank]);
			rank = f;
		}
		else
			break;
	}
}

6. 时间复杂度，O(logn)。不难看出插入的结点在一层一层地向上升（与父结点互换位置），而完全二叉树的高度为logn，故其时间复杂度为O(logn)。

堆的删除与下滤

1. 从一个线性序列中删除一个元素是简单的，但对于堆这样的结构而言，若以比较的方式来删除某一个元素并无意义，堆的有序性告诉我们，从堆中删除掉对顶元素是比较有价值的（时间复杂度O(1)）。不妨将堆的删除操作视为取出堆顶元素。
2. 对于一个堆heap而言，取出对顶元素只需要删除掉heap[0]即可，那么删除掉首元素之后，原来的堆失去了它的跟结点，整个堆面临着失效的尴尬境地。与插入操作类似，需要思考一个问题，如何调整可以使得原堆中其他部分可以依旧保持的原来的结构（各个元素之间的父子关系）？可以在被删除掉的首元素的位置再插入一个元素来保持原堆中其他结点的结构不变，可以将这样的过程视为一个新的结点替换掉了原来的根结点。
3. 那么这个新的结点从何而来呢？若选取了中间的某一结点X来替换掉根结点，则会导致X之后的结点全部失效（原来的结构被破坏）。至此，相信大家不难看出，一如插入操作一般，选取堆底元素来替换根结点是最佳的选择，这使得整个堆依旧可以保持原来的结构。接下来要思考的就是替换之后整个堆是否依旧保持着堆序性。
4. 前面说到堆处处局部的有序即是堆整体的有序，那么在替换之后，局部是否有序便成了判断堆整体是否有序的依据。分别用N、L(N)、R(N)表示替换之后的根结点、根结点的左孩子、根结点的右孩子。如果N < L(N)且N < R(N)，那么堆序性依旧保持；否则堆序性被破坏。不如将上述的条件写成如下的形式：如果N < MIN(L(N), R(N))，那么堆序性依旧保持；否则堆序性被破坏。此种情形与在堆底插入一个元素所造成的堆序性破坏略有不同，那么接下来该思考的是如何调整使得堆的局部恢复有序性呢？是否可以通过类似于上滤的方案来解决此类失序的问题呢？
5. 还是回到堆序性这个特性上，对于N、L(N)、R(N)这三个结点组成的局部堆而言，只需保证这三者中的最小值处在根结点这个位置上即可保持堆序性。至此，可以得出若N < MIN(L(N), R(N))不被满足，则将N与MIN(L(N), R(N))呼唤位置即可保持堆序性。同插入处理，在进行一次调整后还需继续对新形成的局部堆进行调整，循环往复，直至局部堆恢复堆序性或结点N成为了叶子结点。这样的一个过程也称为堆的下滤（percolateDown）。
   代码如下：

template<typanme T>
void percolateDown(T *s, size_t rank, size_t size)
{
	size_t lastInternal = (size-1)/2; //最后一个内部结点的秩
	while (rank < lastInternal) 
	{
		size_t lChild = rank*2+1; //左孩子的秩
		size_t rChild = rank*2+2; //右孩子的秩
		size_t LChild = s[lChild] < s[rChild] ? lChild : rChild; //子结点中最小者才有可能成为父结点
		if (s[lChild] < s[rank])  //若违反堆序性
		{
			swap(s[LChild], s[rank]); //交换
			rank = LChild;  //继续考察
		}
		else 
			break;
	}
	
	if (rank == lastInternal)  //如果被调整成了最后一个内部结点，则需要判断是否有右孩子
	{
		size_t lChild = rank*2+1;
		size_t rChild = rank*2+2;
		size_t LChild = s[lChild] < s[rChild] ? lChild : rChild;
		if (rChild == size) //右孩子越界
			LChild = lChild;
		else
			LChild = s[lChild] < s[rChild] ? lChild : rChild;
		if (s[LChild] < s[rank])
			swap(s[Lchild], s[rank]);
	}
}

6. 时间复杂度，渐进意义上O(logn)，其内部操作比上滤过程而言要多一些，故其常系数部分略高。

利用一个已有的序列建立一个堆

1. 这个问题可以通过建立一个空堆，然后逐个将序列中的元素插入至堆中来完成，大致地可以得出时间复杂度为O(nlogn)。如果将这样的操作原地进行，则相当于依次从首元素到尾元素执行上滤操作，暂且将这样的方式称之为自上而下的上滤。
2. 是否可以使用下滤来实现这一功能呢？从最后一个内部结点开始，逐个对所有的内部结点进行下滤操作，完成后就可以得到一个堆。
3. 在此，不妨将对内部结点下滤的过程视为该内部结点与其左右子堆的合并成一个堆的过程。设内部结点为N，左右子堆分别用HL和HR来表示。既是堆，那么HL与HR都满足堆序性，事实上在从最后一个内部结点开始时，HL与HR都至多包含一个元素，只拥有一个元素的堆自然是有序的。等到所有叶子结点的父结点都与其左右子堆（堆中只有一个元素）合并后，才会出现HL和HR中包含多个元素的情况，而经过下滤调整的子堆都是满足堆序性的。至此可以证明通过这样的方式可以使得整个堆恢复堆序性。不妨将这样的方式称之为自下而上的上滤。
4. 时间复杂度为O(n)，是的这可能与大家直观的感觉不一致，证明过程需要使用归纳法，在此就不进行下去了。不过呢可以通过与自上而下的上滤算法来进行简单的对比：首先上滤建堆需要对所有的元素都执行上滤操作，而且越是接近堆底的元素可能需要交换的次数就越多，这意味这可能会有较多的元素需要进行较多次数的交换；而下滤建堆只需对所有内部结点进行下滤操作，这在操作的元素数量上就少了一半，其次越接近堆底的内部结点所需要的交换次数越少，这意味大多数的内部结点只需执行较少的交换，只有离堆顶越近的元素才需要较多的交换，而越接近堆顶，元素数量越少。由此可以看出自下而上的下滤建堆算法在时间复杂度的渐进意义上来讲要优于自上而下的上滤算法。事实上自下而上的下来吧建堆算法称之为弗洛伊德建堆法。
   代码如下

template<typename T>
void heapify(T *s, size_t size)
{
    int rank;
    auto getLastInternal = [size] {return (size-1)>>1;};
    if ((rank = getLastInternal()) < 0) //获取最后一个内部节点
        return ;
        
    while (rank>= 0)  //对每一个内部结点做下滤
    {
        percolateDown(s, rank, size);
        --rank;
    }
}

记录学习历程，各路大神若有指教，可留言探讨，感激不尽！

数组可以看成是一个完全二叉树，大根堆是一个完全二叉树

构造大根堆

例子1：[O(N)---->从下到上]

因为堆是对父节点-左/右孩子节点之间的约束，所以从最后一个非叶子节点开始调整。

注意每次交换后，都要对下一层的子堆进行递归调整，因为交换后有可能破坏已调整子堆的结构。
堆排序

例子2：[O(N)---->从下到上]

1、假设给定无序序列结构如下

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。【9下沉之后，9变成了叶子节点，因此不会对子叶产生影响】

4.找到第二个非叶节点4 【3/2 - 1 = 0】，由于[4,9,8]中9元素最大，4和9交换。【4下沉之后，变动了的子树必须重新调整】

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

此时，我们就将一个无需序列构造成了一个大顶堆。

图解排序算法(三)之堆排序

第3个例子【从上到下 】

从一个空的二叉树开始：

从头开始遍历数组：

for(int i = 0; i < arr.length; i++){
	选出arr[i]，插入二叉树
}

第一次循环：当前需要插入的索引是0，令cur = 0，它的父节点parent = (cur - 1) / 2 = 0 。

• arr[父节点索引] == arr[当前节点索引] ，因此进入下一轮循环
  
  第二次循环：当前需要插入的数据索引是1【需要插入的二叉树的位置索引也是1】，令cur = 1，它的父节点索引是 parent = (cur - 1) / 2 = 0，
• arr[cur] 与arr[parent]比较，因为 当前节点值 > 父节点值，因为需要最大值登顶，因此进入内循环：
  • 交换 当前节点和父节点的值
  • 将当前索引指向父节点，重新计算父节点
  • 因为cur = 0， par = 0，两者相等，因此跳出内循环

进入下一轮循环


第三次循环：需要插入的索引为2，令cur = 2，其父节点 par = (2 - 1)/2 = 0，

• 当前索引值73与父节点值25比较，当前索引比较大，进入内循环：
  • 交换当前节点与父节点的值
  • 当前索引指向父节点索引，重新计算父节点的索引
  • 因为cur = 0， par = 0，因此跳出循环

第4次循环，需要插入的索引为3，令cur =3，其父节点 par = (3 - 1)/2 = 1，

• 当前索引值98与父节点值10比较，当前索引比较大，进入内循环：
  • 交换当前节点与父节点
  • 令cur = 夫节点 = 1，重新计算父节点 par = 0
    
    

判断是否还是在内循环中：

• 当前cur = 1， par = 0，因为当前节点98比父节点73大，进入内层循环
  • 交换98和73的位置
  • 令cur = 父节点的索引 = 0， 重新计算par = (cur -1) / 2 = 0
    
    
    
    第4次循环，需要插入的索引为4，令cur =4，其父节点 par = (4- 1)/2 = 1，
    
    
    
    
    
    
    

第5次循环，需要插入的索引为5，令cur =5，其父节点 par = (5- 1)/2 = 2，





**** 一直循环，直到当前数组循环完毕

总结： 上面的过程可以看成是向数组中不断插入一个元素【向大根堆中插入一个元素】，总结上面经验得知：

• 元素的插入索引是固定的【一定都是size】，但是插入的位置是不一定的。
  • 如果插入的数据小于等于他的父索引【(size - 1)/2】，什么也不干
  • 如果插入的数据大于它的父索引【(size - 1)/2】，那么就让这个数据不断上浮，直到找到了应该的位置就表示插入成功了

节点上浮：当我们在向最大堆中插入一个节点时，我们必须满足完全二叉树的标准，那么被插入节点的位置是固定的，而且要满足父节点关键值不小于子节点关键值，那么我们就需要去移动父结点和子结点的相互位置关系。

堆排序动画

堆排序

例子1：

进行调整后，堆顶元素（array[0]）为最大值，将最大值与堆尾部元素（array[count-1]）交换，并将count值减去1，则此时得到新的无序数组array[count]，此时的堆被破坏；

对应到数组元素为：

调整堆：与建堆过程类似，堆顶元素被一个比较小的值代替，所以从堆顶元素开始调整，在堆顶、堆顶的左孩子、堆顶的右孩子中找出最大的与堆顶进行交换，被交换的元素再次与他下一层的左右孩子进行比较（递归）调整。

然后一直重复，直到count = 0

例子2：

如果要排序：我们一般从最上面的那个元素开始。

从0开始遍历数组：

令cur = 0， 并且cur 与 size - 1的元素交换位置，

代码实现

大根堆进行从大到小的排序

public class TreeNode {
    // 从最后一个非叶子节点开始调整，调整为一个大根堆
    private static void BuildMaxHeap(int[]arr){
        if (arr == null || arr.length < 2){
            return;
        }

        for (int i = arr.length/2 - 1; i > -1; i--){
            adjustMaxHeap(arr, arr.length, i);
        }


        for (int i = arr.length; i > 0; i--){
            swap(arr, i - 1, 0);
            adjustMaxHeap(arr, i - 1, 0);
        }
    }

    private static void adjustMaxHeap(int[]arr, int size, int i){
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max = i;

        if (left < size && arr[left] > arr[max]){
            max = left;
        }

        if (right < size && arr[right] > arr[max]){
            max = right;
        }

        if (max != i){
            swap(arr, i, max);
            adjustMaxHeap(arr, size, max);
        }
    }

    private static void swap(int []arr, int i, int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{23,19,81,79,89,83,17,48,55,26};
        BuildMaxHeap(arr);

        System.out.println(Arrays.toString(arr));
    }
}

大根堆中可能用到的行为

    // 从最好一个非叶子节点开始调整
    // 下移过程
    /**
     * 将父节点为aar[i]的子树调整为最大堆
     * @param arr 堆数组
     * @param size 堆数组长度
     * @param index 节点索引
     */
    private static void AdjustHeap(int[] arr, int size, int index){
        if (arr == null || index < 0){
            return;
        }
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int max = index;
        if (left < size && arr[left] > arr[index]){
            max = left;
        }
        if (right < size && arr[right] > arr[index]){
            max = right;
        }

        if (max != index){
            Swap(arr, max, index);
            AdjustHeap(arr, size, max);
        }
    }


    /**
     * 根据输入的数组构建一个最大堆
     * @param arr 堆数组
     * @param size 堆数组长度
     * @return 堆数组长度
     */
    private static int BuildMaxHeap(int arr[], int size) {
        //对每一个非叶节点开始向下进行最大堆调整
        for (int i = size / 2 - 1; i >= 0; i--)
        {
            AdjustHeap(arr, size, i);
        }
        return size;
    }

    /**
     * 向指定的最大堆中插入节点：首先在堆的最后添加一个节点，然后沿着堆树上升，直到堆树再次调整为最大堆
     * @param arr
     * @param size
     * @param data
     * @return
     */
    int MaxHeapInsert(int arr[], int size,int data)
    {
        int index=size;
        while (index>0 && data>arr[(index-1)/2])
        {
            arr[index]=arr[(index-1)/2];
            index=(index-1)/2;
        }
        arr[index]=data;
        return (size+1);
    }

    /**
     * 最大堆堆顶节点的删除:将堆树中待删除的节点A与堆树中的最后一个节点B互换，然后调整节点B到合适的位置，最后从堆树中删除排在堆数组最后的节点A。
     * @param arr 最大堆数组
     * @param size 堆数组长度
     * @return 删除后的堆数组长度
     */
    private static int MaxHeapDelete(int arr[], int size)
    {
        if(size<=0)return -1;
        Swap(arr, 0, size - 1);
        AdjustHeap(arr,size-1,0);//调整堆为最大堆
        return size-1;
    }

    private static  void Swap(int arr[], int i, int j)
    {
        int temp=arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void main(String[] args) {
        int[] arr = new int[]{23,19,81,79,89,83,17,48,55,26,16,1,46,95,10};
        BuildMaxHeap(arr, arr.length); //[95, 89, 81, 79, 26, 83, 23, 48, 55, 19, 16, 1, 46, 17, 10]

        System.out.println(Arrays.toString(arr));
    }

参考

代码写的很清晰

写得非常好，但是还没有看完

堆排序动画

堆

什么是堆？

堆 是一棵 完全二叉树：即使它不是满二叉树，也是正在从左往右变满的过程中。

1）堆结构就是用数组实现的完全二叉树结构

2）完全二叉树中，如果每棵子树的 最大值都在顶部，是 大根堆

3）完全二叉树中，如果每棵子树的 最小值都在顶部，是 小根堆

4）堆结构的 heapInsert 与 heapify 操作

5）堆结构的增大和减少

6）优先级队列结构，就是堆结构

7）特点：由 N 个数 组成的堆，高度是 log(n)

如何用数组存放堆？

如果从 0 位置开始：

i 层，则

• 左孩子：2 * i + 1
• 右孩子：2 * i + 2
• 父节点：(i - 1) / 2

如果从 1 位置开始：

正是由于可以使用 位运算 来代替 算数运算，效率更高，所以有时候让下标从 1 开始。

• 左孩子：2 * i （i << 1）
• 右孩子：2 * i + 1 （i << 1 | 1）
• 父节点：i / 2 （i >> 1）

如何将数组转化成大根堆？—— heapInsert 操作

每在 i 位置加入一个新的节点，都与它的 (i - 1) / 2 位置的父节点比较，如果比父节点大，则交换（并while比较父节点与父父节点）

private void heapInsert(int[] arr, int index) {
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}
private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

如何返回并删除大根堆的最大值，剩余数字依然保持大根堆？—— heapify 操作

1. 将顶部元素取出
2. 将大根堆的最后位置上的元素覆盖到顶部
3. while 循环
   1. 如果左右孩子中较大的数比当前节点更大，则交换当前节点和较大的孩子节点
   2. 如果左孩子下标越界，或左右孩子都不比当前节点大，就停止

// 返回最大值，并在大根堆中把最大值删掉，剩下的数依然保持大根堆形态
public int pop() {
    int ans = heap[0];
    swap(heap, 0, --heapSize);
    heapify(heap, 0, heapSize);
    return ans;
}
// 从index位置开始，不断的下沉，直到我的孩子都不再比我大，或者我已经没孩子了，就停止
private void heapify(int[] arr, int index, int heapSize) {
    int left = index * 2 + 1;
    while (left < heapSize) {
        // largest存储左右孩子 较大者 的下标
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        // largest存储两个孩子与父节点 较大者 的下标
        largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) { // 不需要交换的情况
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}

堆排序

1. 先让整个数组都变成大根堆结构，建立堆的过程:
   1. 从上到下的方法，时间复杂度为O(N*logN)
   2. 从下到上的方法，时间复杂度为O(N)
2. 把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N*logN)
3. 堆的大小减小成0之后，排序完成！

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 方法1：对数组进行堆排序 O(N*logN)
    for (int i = 0; i < arr.length; i++) { // O(N)
        heapInsert(arr, i); // O(logN)
    }
    // 方法2：仅将数组转化成大顶堆 O(n) 
    for (int i = arr.length - 1; i >= 0; i--) {
        heapify(arr, i, arr.length);
    }
}

语言提供的堆结构 vs 手写的堆结构，怎么选择？

取决于你有没有 动态改信息 的需求！

• 语言提供的堆结构，如果你动态改数据，不保证依然有序

• 手写堆结构，因为增加了对象的位置表，所以能够满足动态改信息的 resign 需求（以后我们的 Dijskra 会用到），而系统自带的堆结构即使是实现了对数据的修改，时间复杂度也不会好，因为它没有 hashmap，只能从顶部开始，遍历每个元素进行 heapify

  public static class MyHeap<T> {
      private ArrayList<T> heap;			  	  // 用动态数组存堆
      private HashMap<T, Integer> indexMap; 	  // 对象的位置表
      private int heapSize;	              	  // 堆大小
      private Comparator<? super T> comparator; // 自定义比较器
      
      /*...省略push,pop,heapInsert,heapify等...*/
      public void resign(T value) { // resign操作不需要全量遍历整个堆
         int valueIndex = indexMap.get(value);
         heapInsert(valueIndex); // 这个heapInsert和下面的heapify，只会命中一个，另一个直接返回
         heapify(valueIndex, heapSize);
      }
  }
  public static void main(String[] args) {
      myHeap = new MyHeap<>(new StudentComparator());
  	/*...省略s1, s2等new对象过程...*/
      myHeap.push(s1);
      myHeap.push(s2);
      myHeap.push(s3);
      myHeap.push(s4);
      myHeap.push(s5);
  
      s2.age = 6;
      myHeap.resign(s2);
  }
  

PriorityQueue 底层就是用堆实现的，默认是小根堆

public static void main(String[] args) {
    // 小根堆
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    heap.add(5);
    heap.add(7);
    heap.add(3);
    heap.add(0);
    heap.add(2);
    heap.add(5);
    while (!heap.isEmpty()) { // 排序输出
        System.out.println(heap.poll());
    }
}

与堆有关的题目

已知一个几乎有序的数组。

几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k（假设k=5），并且k相对于数组长度来说是比较小的。

请选择一个合适的排序策略，对这个数组进行排序。

思路：维护一个大小为 k 的小根堆，每加入一个新数字，先将小根堆的最小值弹出，再把新值放入小根堆中去。

public static void sortedArrDistanceLessK(int[] arr, int k) {
    if (k == 0) {
        return;
    }
    // 默认小根堆，复杂度：log(k)
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    int index = 0;
    for (; index <= Math.min(arr.length - 1, k - 1); index++) {
        heap.add(arr[index]);
    }
    int i = 0;
    for (; index < arr.length; i++, index++) {
        heap.add(arr[index]);
        arr[i] = heap.poll();
    }
    while (!heap.isEmpty()) {
        arr[i++] = heap.poll();
    }
}

比较器 Comparator

1)比较器的实质就是重载比较运算符

2)比较器可以很好的应用在特殊标准的排序上

3)比较器可以很好的应用在根据特殊标准排序的结构上

4)写代码变得异常容易，还用于范型编程

public static class IdAscendingComparator implements Comparator<Student> {
    // 返回负数，第一个参数排在前面
    // 返回正数，第二个参数排在前面
    // 返回0的时候，谁在前面无所谓
    @Override
    public int compare(Student o1, Student o2) {
        return o1.id - o2.id;
    }
}
public static void main(String[] args) {
    Student student1 = new Student("A", 2, 20);
    Student student2 = new Student("B", 3, 21);
    Student student3 = new Student("C", 1, 22);
    Student[] students = new Student[]{student1, student2, student3};
    Arrays.sort(students, new IdAscendingComparator());
}

用 Comparator 排序：

public static class HeapComp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}
public static void main(String[] args) {
    Integer[] arr = {5, 4, 3, 2, 7, 9, 1, 0};
    Arrays.sort(arr, new HeapComp());
}