[TOC]

1、优先队列

优先队列是一种高效实现插入和删除最大元素（或者是最小元素）的数据结构，堆是它的高效的实现，两种操作的时间复杂度均为O(log n)

2、典型的应用

• 在N个数中找出最大的K个数（top k）
• 堆排序

3、基于堆高效的实现优先队列

a、一些概念

• 堆有序：一个二叉树的每个结点都大于它的两个子节点，则称这个二叉树堆有序 -->一个堆有序的二叉树的根节点是所有结点中最大的
• 二叉堆：我的理解是一个堆有序的完全二叉树，简称堆。二叉堆的用数组存储（不使用数组的第一个元素），一个大小为N的完全二叉树的高度为log N

b、关键的步骤

• 使得堆有序化的两个操作：上浮（swim）和下沉(sink)
• 插入元素：将新的元素加到数组的末尾,并使这个元素上浮到合适的位置
• 删除最大元素：将数组顶端的元素删去并将最后一个元素放到顶端，然后使之下沉到合适的位置

c、代码实现

/*
 * <p>
 * 优先队列的实现（基于堆）
 * <p>
 * 问题：  //items = new Item[5];    为什么这样写会报错
 */
public class MaxPQ<Item extends Comparable<Item>> {

    private int N;   //堆中元素的个数
       private int maxN;
    private Item[] items;  //存储完全二叉树的数组

    public MaxPQ(int maxN) {
        this.maxN = maxN;
        items = (Item[]) new Comparable[maxN + 1]; 
        //items = new Item[5];    
    }

    //删除最大元素
    public Item delMax() {

        if (isEmpty()) return null;
        Item max = items[1];
        items[1] = items[N--];
        items[N + 1] = null;
        sink(1);

        return max;
    }

    //插入元素
    public void insert(Item item) {
        if (item == null) throw new NullPointerException("插入元素为空！");
       /* if(N >= maxN){
            if (less(items[N],item)) items[N] = item;
        }else{
            items[++N] = item;
        }*/
        items[++N] = item;
        swim(N);
        //printAr();
    }

    private boolean less(Item item, Item item1) {
        return item.compareTo(item1) < 0;
    }

    //上浮
    private void swim(int k) {
        while (k > 1) {
            if (less(k / 2, k))
                swap(k, k / 2);
            k /= 2;
        }

        //其实这样写更好
        /*while(k > 1 && less(k / 2,k)){
            swap(k,k / 2);
            k /= 2;
        }*/
    }


    //下沉
    private void sink(int k) {
            while(2 * k <= N){
                int j = 2 * k;
                if(j < N && less(j,j + 1)) j ++;
                if (!less(k,j))  break;
                swap(k,j);
                k = j;
       }
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    /**
     * 几个辅助函数
     */

    private void swap(int k, int i) {
        Item tmp = items[k];
        items[k] = items[i];
        items[i] = tmp;
    }

    private boolean less(int i, int k) {
        return items[i].compareTo(items[k]) < 0;
    }

    public void printAr(){
        System.out.println(Arrays.toString(items));
    }
}

4、在N个数字中找到最大的M个数大概的思路（用最小堆）

• 将N个数字逐一插入到最小堆中； //插入
• 如果堆中的元素的个数超过了M，则删除最小的元素，直到读完N个数据 //删除优先级最高的元素

剩下的M个元素就是N个数字中最大的M个

5、利用系统自带的PriorityQueue来实现在N个数字中找到最大的M个,这里要用最小堆

PriorityQueue represented as a balanced binary heap(平衡二叉堆),PriorityQueue默认是用最小堆的实现（java默认将最小值放到前面），在它的构造方法里面传一个Collections.reverseOrder()就是一个最大堆的实现

代码:

 /**
 *
 * 主要是为了在N个数字中找到最大的M个
 *
 * 要找到N个数字中最大的M个要用最小堆，相反要找到N个数字中最小的M个数字要用最大堆。
 *
 * 大概的思路（在N个数字中找到最大的M个）：
 *
 *          将N个数字逐一插入到最小堆中；
 *          如果堆中的元素的个数超过了M，则删除最小的元素，直到读完N个数据
 *
 *    剩下的M个元素就是N个数字中最大的M个
 */
public class TestTopM {

    public static void main(String[] args) {
        TestTopM t = new TestTopM();

        //测试PriorityQueue
      // t.testPriorityQueue();

        //测试MaxPQ
        t.testMaxPQ();


        //测试排序
        // t.testOrder();


    }

    /**
     * java默认是给基本类型的数据从小到大排序
     * <p>
     * 要给基本类型的数据按从大到小的顺序来排，可以使用包装类并传Collections.reverseOrder()参数；
     * 但是这样涉及到数据的装箱与拆箱,所以建议先从小到大排序，然后再逆序
     */

    private void testOrder() {

        Integer[] ar = {1, 6, 3, 2, 10, 13, 23};
        System.out.println(Arrays.toString(ar));
        Arrays.sort(ar, Collections.reverseOrder());
        System.out.println(Arrays.toString(ar));
    }

    private void testMaxPQ() {

        int M = 5;
        MaxPQ<Integer> queue = new MaxPQ<>(M + 1);  //由于MaxPQ维护数组的第一个元素没有用到
        int[] ar = ArrayUtils.randomArray(10, 1, 15);
        ar = new int[]{1, 6, 9, 15, 5, 8, 13, 9, 11, 14};
        System.out.println("原数组 ：" + Arrays.toString(ar));
        for (int i = 0; i < ar.length; i++) {

            queue.insert(ar[i]);
            if (queue.size() > M) queue.delMax();

        }

        Arrays.sort(ar);

        System.out.println("排序后的数组 ：" + Arrays.toString(ar));
        System.out.println("队列的长度 ：" + queue.size());

        //为了从大到小到小输出
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        while(!queue.isEmpty()){
            stack.push(queue.delMax());
        }

        while (!stack.isEmpty()){
            System.out.print(stack.poll() + ",");
        }
    }

    /**
     * 利用jdk自带的PriorityQueue来实现在N个数字中找到最大的M个,这里要用最小堆
     * <p>
     *  a、PriorityQueue represented as a balanced binary heap（平衡二叉堆）
     *  b、PriorityQueue默认是用最小堆的实现（java默认将最小值放到前面），在构造方法里面传一个
     * Collections.reverseOrder()就用一个最大堆的实现
     *  c、插入元素：offer()、add()  找出并删除优先级最高的元素：poll()  找出优先级最高的元素：peek()
     */
    void testPriorityQueue() {
        int M = 4;
        //PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int[] ar = ArrayUtils.randomArray(10, 1, 15);
        System.out.println("原数组 ：" + Arrays.toString(ar));
        for (int i = 0; i < ar.length; i++) {
            queue.offer(ar[i]);
            if (queue.size() > M) queue.poll();
        }

        Arrays.sort(ar);
        ArrayUtils.inverseArray(ar);

        System.out.println("排序后的数组 ：" + Arrays.toString(ar));
        System.out.println("队列的长度 ：" + queue.size());

        //为了从大到小到小输出
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        while(!queue.isEmpty()){
            stack.push(queue.poll());
        }

        while (!stack.isEmpty()){
            System.out.print(stack.poll() + ",");
        }

    }
}

6、基于堆的排序

• 思路一：利用辅助空间进行：把数组的元素依次放到一个堆里面，然后把堆中的元素放到数组中去，这样的话，从小到大排序要用到的是最小堆。这样做牺牲了一点的空间复杂度为O(N)，虽然简单，但是浪费空间
• 思路二:原地堆排序
  分为两步：
  a.原地构造堆：从完全二叉树中最后一个叶子节点的的父节点开始（一个节点的树就是一个堆），先构造以这个节点为根节点的堆，重复次步骤直至根节点;
  这样每个被遍历到的结点的子树都是一个堆，所以每次构造堆就只要一次sink操作即可
  b.下沉排序: 依次交换第一个和最后一个元素，然后下沉第一个元素使得除了被换到后面的元素堆有序，直到所有元素都到被交换过 ，由于第一个是优先级别最大的，
  所以下沉排序后的数组的顺序和原来的优先级的顺序相反
  这样的实现比较复杂，但是空间复杂度为O（1）
  c.堆排序源代码：

      /**
 *
 * 利用优先队列的高效找出最大(或者最小)元素进行排序（要用到缓存数组，不知道这样叫不叫堆排序）
 *
 */
public class HeapSort {

    public static void main(String[] args) {

        int[] ar = ArrayUtils.randomArray(10,1,20);
        //ar = new int[]{0,1,2,3,4,5,6,7,8};
        System.out.println("原数组 ：" + Arrays.toString(ar));
        //sort(ar);
        sortInPlace(ar);
        System.out.println("变化后的数组：" + Arrays.toString(ar));
    }

    //使用系统自带的优先队列和实现堆排序
    public static void sort(int[] ar){
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i : ar)   queue.offer(i);
        for (int i = 0; i < ar.length; i++)  ar[i] = queue.poll();
    }

    /**
     *  原地实现堆排序(从小到大的排序和最大的的sink一致)
     *
     *  分为两步，第一步：堆的构造，第二步：下沉排序
     *
     *  注意:这里有用数组的第一个位置来存储元素
     */
    public static void sortInPlace(int[] ar){
        int N = ar.length;
        //堆的构造
        for (int k = (N - 2) / 2; k >= 0; k--)   sink(ar,k,N - 1);

        /*System.out.println("堆有序化的数组 ：" +Arrays.toString(ar));
        System.out.println("-------------------------");*/
        //下沉排序
        while(N > 0){
            ArrayUtils.swap(ar,0,-- N);
            sink(ar,0,N - 1);
        }

    }

    private static void sink(int[] ar, int from, int to) {

       // System.out.println("from =" + from);
        while((2 * from + 1) <= to){
            //System.out.println(Arrays.toString(ar) + "  ,from =" +  from);
            int k = 2 * from + 1;
            if (k < to && less(ar[k],ar[k + 1])) k ++;
            if(!less(ar[from],ar[k]))  break;
            ArrayUtils.swap(ar,from,k);

            from = k;

        }

    }

    private static boolean less(int i, int j) {
        return i < j;
    }

}