数据结构------优先级队列(堆)

堆
概念:

1. 堆逻辑上是一棵完全二叉树
2. 堆物理上是保存在数组中
3. 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆
4. 反之，则是小堆，或者小根堆，或者最小堆
5. 堆的基本作用是，快速找集合中的最值

如何构建一个堆呢?

首先建堆需要借助一个调整的过程,根据需要向上或者向下调整根节点的位置,然后从第一个非叶子节点开始进行调整,就可以得到一个堆.

代码实现:

	//从最后一个非叶子节点进行向下调整;
	public static void creatHeap(int[] n,int size){
        for (int i=(size-1)/2; i >= 0;i--) {
            shiftDown(n,size,i);
        }
    }
    //向下调整;
    public static void shiftDown(int[] n,int size,int parent){
        int left = parent * 2 +1;
        while (left < size){
            int right = parent * 2 + 2;
            int max = left;
            if(right < size){
                if(n[right] > n[left]){
                    max = right;
                }
            }
            if (n[parent] >= n[max]){
                break;
            }
            swap(n,parent,max);
            parent = max;
            left = max * 2 + 1;
        }
    }

堆的应用
一.优先级队列
在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。
在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列
二.TOPK问题

问题:在N个数中找到最大的K个数.

1.先建一个K大小的堆;
2.再将数组中的数字一次与根节点比较大于根节点交换再进行调整;

//在N个数中找到K个最大的数;
    //先将前K个数建立一个小根堆;
    //依次将剩余的数一个个进行比较,若大于根则替换在向下调整,否则就下一个数;
    //最后堆中元素就是前K个最大的数;
    public static void swap(int[] array,int a,int b){
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
    public static void shiftDown(int[] array,int index){
        int left = index * 2 +1;
        while (left < array.length){
            int min = left;
            int right = index * 2 + 2;
            if (right < array.length){
                if (array[left] > array[right]){
                    min = right;
                }
            }
            if (array[index] < array[min]){
                break;
            }
            swap(array,index,min);
            index = min;
            left = index * 2 + 1;
        }
    }
    public static void creatHeapK(int[] array){
        for (int i =(array.length - 1) / 2; i >= 0 ; i--) {
            shiftDown(array,i);
        }
    }
    public static int[] topK(int[] n,int k){
        int[] topK = new int[k];
        System.arraycopy(n, 0, topK, 0, k);
        creatHeapK(topK);
        for (int i = k; i <n.length; i++) {
            if (n[i] > topK[0]){
                topK[0] = n[i];
                shiftDown(topK,0);
            }
        }
        return topK;
    }
    public static void main(String[] args) {
        int[] n = {1,3,9,4,6,8,2,5,7,10};
        System.out.println(Arrays.toString(topK(n,3)));
    }

三.堆排序

先建好一个大堆或小堆,每次将堆顶元素与堆尾交换,堆的大小减一,再进行调整;
如此反复就实现了排序;
代码在另一篇排序博客里可以找到;