堆的介绍与应用

1、堆的简介

Heap是一种数据结构：
1）完全二叉树；
2）heap中存储的值是偏序；
最大堆：最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值。
图片说明
最小堆：最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值。

堆的根节点叫堆顶。
最大堆的堆顶是整个堆中最大元素；最小堆的堆顶是整个堆中最小元素。

2、堆的操作

2.1 堆的数据结构

存储结构：一般是由数组来表示堆，i节点的父节点下标就为(i-1)/2。它的左右节点下标分别为 2*i+1 和 2*i+2。该性质有对的逻辑结构为完全二叉树得来。
图片说明

2.2 插入节点（Insert）

当二叉树插入节点时，插入的位置是完全二叉树的最后一个位置。例如插入一个新的节点2。
图片说明
这时，新的节点的父节点10比5大，显然不符合最小堆的性质。于是让新节点"上浮"，和父节点交换位置。

继续用节点2和父节点7比较，因为2小于7，则让新节点继续"上浮"。

继续比较，最终新节点2"上浮"到堆顶位置。

插入操作在数据存储结构形式变化：
图片说明

"上浮（swim）"操作的实现：

/**
  * “上浮”调整
  * 时间复杂度 O(logn)
  * @param array  待调整的堆
  */
public void upAdjust(int[] array){
    int childIndex=array.length-1;
    int parentIndex=(childIndex-1)/2;
    //temp保存插入的叶子节点值，用于最后的赋值
    int temp=array[childIndex];
    while(childIndex>0&&temp<array[parentIndex]){
        //无须真正交换，单向赋值即可
        array[childIndex]=array[parentIndex];
        childIndex=parentIndex;
        parentIndex=(parentIndex-1)/2;
    }
    array[childIndex]=temp;
}

2.3 删除节点（Delete）

二叉树删除节点的过程和插入节点的过程正好相反，所删除的是处于堆顶的节点。例如删除最小堆的堆顶节点2。
图片说明
这时，为了继续维持完全二叉树的结构，我们把堆的最后一个节点10临时补到堆顶的位置。

接下来，让暂处堆顶位置的节点10和它的左、右孩子进行比较，如果左、右孩子中最小的一个（显然是节点5）比节点10小，那么让节点10"下沉"。
图片说明
接下来继续让节点10和它的左、右孩子做比较，左、右孩子中最小的是节点7，由于10大于7，让节点10继续"下沉"。

这样一来，二叉树重新得到了调整。

插入操作在数据存储结构形式变化：
图片说明

"下沉（link）"操作的实现：

/**
 * “下沉”调整
 * 时间复杂度 O(logn)
 * @param array            待调整的堆
 * @param parentIndex      要“下沉”的父节点
 * @param length           堆的有效大小
 */
public void downAdjust(int[] array,int parentIndex,int length){
    //temp保存父节点值，用于最后的赋值
    int temp=array[parentIndex];
    int childIndex=2*parentIndex+1;
    while(childIndex<length){
        //如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
        if(childIndex+1<length&&array[childIndex+1]<array[childIndex]){
            childIndex++;
        }
        //如果父节点小于任何一个孩子的值，则直接跳出
        if(temp<=array[childIndex]){
            break;
        }
        array[parentIndex]=array[childIndex];
        parentIndex=childIndex;
        childIndex=2*childIndex+1;
    }
    array[parentIndex]=temp;
}

2.4 构建二叉堆（Build）

构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次"下沉"。
下面举一个无序完全二叉树的例子，如下图所示。
图片说明
首先，从最后一个非叶子节点开始，也就是从节点21开始。如果节点21大于它左、右孩子中最小的一个，则节点21"下沉"。

接下来，轮到节点9，如果节点9大于它左、右孩子节点中最小的一个，则节点9"下沉"。

然后轮到节点5，如果节点5大于它左、右孩子节点中最小的一个，则节点5"下沉"。事实上节点5小于它的左、右孩子，所以不用改变。
接下来轮到节点15，如果节点15大于它的左、右孩子节点中最小的一个，则节点"下沉"。
图片说明
节点15继续比较，继续"下沉"。

经过上述几轮比较和"下沉"操作，最终每一节点都小于它的左、右孩子节点，一个无序的完全二叉树就被构建成了一个最小堆。

"构建堆"的操作实现：

/**
 * 构建堆
 * 时间复杂度 O(n)
 * @param array  待调整的堆
 */
public void buildHeap(int[] array){
    for(int i=(array.length-2)/2;i>=0;i--){
        downAdjust(array,i,array.length);
    }
}

3堆的应用一优先队列

3.1 定义

最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队。
最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队。
###3.2 实现
通过最大堆的定义可知，最大堆的堆顶是整个堆中的最大元素。因此可以用最大堆来实现最大优先队列。
图片说明
入队操作：
1.插入新的节点20；

2.新节点"上浮"到合适的位置。
出队操作：
1.让原堆顶节点21出队;

2.把最后一个节点10替换到堆顶位置;

3.节点10"下沉"，节点20成为新堆顶。

3.3代码实现

import java.util.Arrays;
public class PriorityQueue {
    private int[] array;
    private int size;
    public PriorityQueue(){
        //队列初始化为32
        array=new int[32];
    }

    /**
     * 入队
     * 时间复杂度 O(logn)
     * @param key  入队元素
     */
    public void enQueue(int key){
        //队列长度超出范围，扩容
        if(size >= array.length){
            resize();
        }
        array[size++]=key;
        upAdjust();
    }

    /**
     * 出队
     * 时间复杂度 O(logn)
     * @return
     * @throws Exception
     */
    public int deQueue() throws Exception{
        if(size<=0){
            throw new Exception("the queue is empty");
        }
        //获取堆顶元素
        int head=array[0];
        //让最后一个元素移动到堆顶
        array[0]=array[--size];
        downAdjust();
        return head;
    }

    private void resize(){
        //队列容量翻倍
        int newSize=this.size*2;
        this.array= Arrays.copyOf(this.array,newSize);
    }

    /**
     * “上浮”调整
     */
    public void upAdjust(){
        int childIndex=size-1;
        int parentIndex=childIndex/2;
        //temp保存插入的叶子节点值，用于最后的赋值
        int temp=array[childIndex];
        while(childIndex > 0 && temp > array[parentIndex]){
            //无须真正交换，单向赋值即可
            array[childIndex]=array[parentIndex];
            childIndex=parentIndex;
            parentIndex=(parentIndex-1)/2;
        }
        array[childIndex]=temp;
    }

    /**
     * “下沉”调整
     */
    public void downAdjust(){
        //temp保存父节点值，用于最后的赋值
        int parentIndex=0;
        int temp=array[parentIndex];
        int childIndex=1;
        while(childIndex<size){
            //如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
            if(childIndex+1 < size && array[childIndex+1] > array[childIndex]){
                childIndex++;
            }
            //如果父节点小于任何一个孩子的值，则直接跳出
            if(temp >= array[childIndex]){
                break;
            }
            //无序真正的交换单向赋值即可
            array[parentIndex]=array[childIndex];
            parentIndex=childIndex;
            childIndex=2*childIndex+1;
        }
        array[parentIndex]=temp;
    }
}

4、堆的应用二堆排序

4.1 堆排序的思想

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
###4.2 堆排序的算法步骤
1.把无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。
2.循环删除堆顶元素，替换到二叉堆的末尾，调整产生新的堆顶；
图片说明
删除节点20，节点19称为新堆顶；

删除节点19，节点17称为新堆顶；

删除节点17，节点15成为新堆顶；

删除节点15，节点13成为新堆顶；

删除节点13，节点10成为新堆顶；

删除节点10，节点9称为新堆顶；

删除节点9，节点7成为新堆顶；
图片说明
删除节点7，节点5成为新堆顶。

到此为止，原本的最大二叉堆已经变成了一个从小到大的有序集合。其数据存储形式变化为：

4.3堆排序的代码实现

/**
 * “下沉”调整
 * @param array            待调整的堆
 * @param parentIndex      要“下沉”的父节点
 * @param length           堆的有效大小
 */
public void downAdjust(int[] array,int parentIndex,int length){
     //temp保存父节点值，用于最后的赋值
     int temp=array[parentIndex];
     int childIndex=2*parentIndex+1;
     while(childIndex<length){
        //如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
        if(childIndex+1 < length && array[childIndex+1] > array[childIndex]){
            childIndex++;
        }
        //如果父节点小于任何一个孩子的值，则直接跳出
        if(temp >= array[childIndex]){
            break;
        }
        array[parentIndex]=array[childIndex];
        parentIndex=childIndex;
        childIndex=2*childIndex+1;
    }
    array[parentIndex]=temp;
}

/**
 * 构建堆  无序数组构建成堆
 * @param array  待调整的堆
 */
public void buildHeap(int[] array){
    for(int i=(array.length-2)/2;i>=0;i--){
        downAdjust(array,i,array.length);
    }
}

/**
 * 堆排序 （升序）
 * 时间复杂度 O(nlogn)
 * @param array  待调整的堆
 */
public void heapSort(int[] array){
    //1. 把无序数组构建成最大堆
    buildHeap(array);
    //2. 循环删除堆顶元素，移到集合尾部，调整堆产生新的堆顶
    for(int i=array.length-1;i>0;i--){
        //最后1个元素和第1个元素进行交换
        int temp=array[i];
        array[i]=array[0];
        array[0]=temp;
        //"下沉"调整最大堆
        downAdjust(array,0,i);
    }
}

5、算法的使用

https://leetcode-cn.com/problems/merge-k-sorted-lists/
leet_code 23合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

代码:

class Solution {
    /**
     * 自定义的优先队列
     */
    public static class PriorityQueue {
        private  ListNode[] array;
        private  int size;
        public  PriorityQueue(){
            //队列初始化为32
            array=new ListNode[32];
        }
        public PriorityQueue(int k){
            //队列初始化为32
            array=new ListNode[k];
        }

        /**
         * 入队
         * 时间复杂度 O(logn)
         * @param node  入队元素
         */
        public void enQueue(ListNode node){
            //队列长度超出范围，扩容
            if(size >= array.length){
                resize();
            }
            array[size++]=node;
            upAdjust();
        }

        /**
         * 出队
         * 时间复杂度 O(logn)
         * @return
         * @throws Exception
         */
        public ListNode deQueue(){
            if(size<=0){
                return null;
            }
            //获取堆顶元素
            ListNode head=array[0];
            //让最后一个元素移动到堆顶
            array[0]=array[--size];
            downAdjust();
            return head;
        }

        private void resize(){
            //队列容量翻倍
            int newSize=this.size*2;
            this.array= Arrays.copyOf(this.array,newSize);
        }

        private boolean isEmpty(){
            return size==0;
        }
        /**
         * “上浮”调整
         */
        public void upAdjust(){
            int childIndex=size-1;
            int parentIndex=(childIndex-1)/2;
            //temp保存插入的叶子节点值，用于最后的赋值
            ListNode temp=array[childIndex];
            while(childIndex > 0 && temp.val < array[parentIndex].val){
                //无须真正交换，单向赋值即可
                array[childIndex]=array[parentIndex];
                childIndex=parentIndex;
                parentIndex=(parentIndex-1)/2;
            }
            array[childIndex]=temp;
        }

        /**
         * “下沉”调整
         */
        public void downAdjust(){
            //temp保存父节点值，用于最后的赋值
            int parentIndex=0;
            ListNode temp=array[parentIndex];
            int childIndex=1;
            while(childIndex<size){
                //如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
                if(childIndex+1 < size && array[childIndex+1].val <= array[childIndex].val){
                    childIndex++;
                }
                //如果父节点小于任何一个孩子的值，则直接跳出
                if(temp.val < array[childIndex].val){
                    break;
                }
                //无序真正的交换单向赋值即可
                array[parentIndex]=array[childIndex];
                parentIndex=childIndex;
                childIndex=2*childIndex+1;
            }
            array[parentIndex]=temp;
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        int num=0;
        for(int i=0;i<lists.length;i++){
            ListNode list=lists[i];
            while(list!=null){
                num++;
                list=list.next;
            }
        }
        PriorityQueue queue=new PriorityQueue(num);
        for(int i=0;i<lists.length;i++){
            ListNode list=lists[i];
            while(list!=null){
                queue.enQueue(new ListNode(list.val));
                list=list.next;
            }
        }
        ListNode head=new ListNode(0);
        ListNode flag=head;
        while(!queue.isEmpty()){
            flag.next=queue.deQueue();
            flag=flag.next;
        }
        return head.next;
    }
}

备注：这里是自己通过堆自定义的优先队列求解的，java中已经有了内置的优先队列，通过import java.util.PriorityQueue;语句引入。

参考

《漫画算法：小灰的算法之旅》

堆（Heap）的介绍与应用