堆排序

堆排序是利用，堆的性质进行数据排序。

• 堆首先是一个完全二叉树。
• 任意子节点比他的父节点要大/小。

堆分为大顶堆和小顶堆。

大顶堆

根节点是整个堆的最大值。任意子节点比父节点要小。

小顶堆

根节点是整个堆的最小值。任意子节点比父节点要大。

数组实现

   private static void buildMaxHeap(int[] array) {
        for (int i = array.length / 2; i >= 0; i--) {
            buildRoot(array, array.length, i, true);
        }
    }

    private static void buildMinHeap(int[] array) {
        for (int i = array.length / 2; i >= 0; i--) {
            buildRoot(array, i, array.length, false);
        }
    }

    private static void buildRoot(int[] arr, int root, int len, boolean isMax) {
        int val = arr[root];
        while (true) {
            int left = root << 1;
            if (left >= len) {
                break;
            }
            int right = left + 1;
            int cur = left;
            if (isMax) {
                if (right < len && arr[left] < arr[right]) {
                    cur = right;
                }
                if (arr[cur] < val) {
                    cur = root;
                }
            } else {
                if (right < len && arr[left] > arr[right]) {
                    cur = right;
                }
                if (arr[cur] > val) {
                    cur = root;
                }
            }
            if (cur == root) {
                break;
            }

            arr[root] = arr[cur];
            root = cur;
        }
        arr[root] = val;
    }

优先级队列实现

       PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });

使用堆排序解决TopN问题

计算数组最大的N个数。将前N个元素构建一个小顶堆，利用小顶堆的特性，小顶堆的根节点永远是堆中最小的元素，从第N+1个元素开始，与小顶堆的根节点进行比较，如果比根节点大，则替换掉根节点，并且重建小顶堆。这样一直到最后一个元素，能保证小顶堆中的元素是数组中最大的N个元素。
计算前N个最小元素。同理构建大顶堆。