二叉堆 Binary Heap：https://blog.csdn.net/qq_40794973/article/details/102532323 

二叉堆 Binary Heap code：https://blog.csdn.net/qq_40794973/article/details/102535924

优先队列：https://blog.csdn.net/qq_40794973/article/details/102536322



什么是优先队列？

普通队列：先进先出；后进后出
	
优先队列：出队顺序和入队顺序无关；和优先级相关
为什么使用优先队列？

在N个元素中选出前M个元素(在1,000,000个元素中选出前100名)

排序？NlogN
	
使用优先队列？NlogM


 


对于总共N个请求

使用普通数组或者顺序数组，最差情况：O(n^2)
	
使用堆：O(nlgn)


 

利用堆进行排序 

 

// 在堆的有关操作中，需要比较堆中元素的大小，所以Item需要extends Comparable
public class MaxHeap<Item extends Comparable> {
    protected Item[] data;
    protected int count;
    protected int capacity;
    // 构造函数, 构造一个空堆, 可容纳capacity个元素
    public MaxHeap(int capacity) {
        data = (Item[]) new Comparable[capacity + 1];
        count = 0;
        this.capacity = capacity;
    }
    // 构造函数, 通过一个给定数组创建一个最大堆
    // 该构造堆的过程, 时间复杂度为O(n)
    public MaxHeap(Item arr[]) {
        int n = arr.length;
        data = (Item[]) new Comparable[n + 1];
        capacity = n;
        for (int i = 0; i < n; i++) {
            data[i + 1] = arr[i];
        }
        count = n;
        for (int i = count / 2; i >= 1; i--) {
            shiftDown(i);
        }
    }
    // 返回堆中的元素个数
    public int size() {
        return count;
    }
    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty() {
        return count == 0;
    }
    // 像最大堆中插入一个新的元素 item
    public void insert(Item item) {
        assert capacity - count >= 1;
        data[count + 1] = item;
        count++;
        shiftUp(count);
    }
    // 从最大堆中取出堆顶元素, 即堆中所存储的最大数据
    public Item extractMax() {
        assert count >= 1;
        Item ret = data[1];
        swap(1, count);
        count--;
        shiftDown(1);
        return ret;
    }
    // 获取最大堆中的堆顶元素
    public Item getMax() {
        assert (count > 0);
        return data[1];
    }
    // 交换堆中索引为i和j的两个元素
    private void swap(int i, int j) {
        Item t = data[i];
        data[i] = data[j];
        data[j] = t;
    }
    //********************
    //* 最大堆核心辅助函数
    //********************
    private void shiftUp(int k) {
        while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {
            swap(k, k / 2);
            k /= 2;
        }
    }
    private void shiftDown(int k) {
        while (2 * k <= count) {
            int j = 2 * k; // 在此轮循环中,data[k]和data[j]交换位置
            if (j + 1 <= count && data[j + 1].compareTo(data[j]) > 0) {
                j++;
            }
            // data[j] 是 data[2*k]和data[2*k+1]中的最大值
            if (data[k].compareTo(data[j]) >= 0) {
                break;
            }
            swap(k, j);
            k = j;
        }
    }
}

 测试 MaxHeap
//MaxHeap<Integer> maxHeap = new MaxHeap<>(100);
//int N = 100; // 堆中元素个数
//int M = 100; // 堆中元素取值范围[0, M)
//for (int i = 0; i < N; i++) {
//    maxHeap.insert(new Integer((int) (Math.random() * M)));
//}
//Integer[] arr = new Integer[N];
 将maxheap中的数据逐渐使用extractMax取出来
 取出来的顺序应该是按照从大到小的顺序取出来的
//for (int i = 0; i < N; i++) {
//    arr[i] = maxHeap.extractMax();
//    System.out.print(arr[i] + " ");
//}
//System.out.println();
 确保arr数组是从大到小排列的
//for (int i = 1; i < N; i++) {
//    assert arr[i - 1] >= arr[i];
//}

 对整个arr数组使用HeapSort1排序
 HeapSort1, 将所有的元素依次添加到堆中, 在将所有元素从堆中依次取出来, 即完成了排序
 无论是创建堆的过程, 还是从堆中依次取出元素的过程, 时间复杂度均为O(nlogn)
 整个堆排序的整体时间复杂度为O(nlogn)
//public static void sort(Comparable[] arr) {
//    int n = arr.length;
//    MaxHeap<Comparable> maxHeap = new MaxHeap<Comparable>(n);
//    for (int i = 0; i < n; i++) {
//        maxHeap.insert(arr[i]);
//    }
//    for (int i = n - 1; i >= 0; i--) {
//        arr[i] = maxHeap.extractMax();
//    }
//}

 对整个arr数组使用HeapSort2排序
 HeapSort2, 借助我们的heapify过程创建堆
 此时, 创建堆的过程时间复杂度为O(n), 将所有元素依次从堆中取出来, 时间复杂度为O(nlogn)
 堆排序的总体时间复杂度依然是O(nlogn), 但是比HeapSort1性能更优, 因为创建堆的性能更优
//public static void sort(Comparable[] arr){
//    int n = arr.length;
//    MaxHeap<Comparable> maxHeap = new MaxHeap<>(arr);
//    for( int i = n-1 ; i >= 0 ; i -- ) {
//        arr[i] = maxHeap.extractMax();
//    }
//}

// 将 ShiftUp 和 ShiftDown 函数使用类似插入排序算法的方式进行优化的最大堆
public class MaxHeapO<Item extends Comparable> {
    protected Item[] data;
    protected int count;
    protected int capacity;
    // 构造函数, 构造一个空堆, 可容纳capacity个元素
    public MaxHeapO(int capacity) {
        data = (Item[]) new Comparable[capacity + 1];
        count = 0;
        this.capacity = capacity;
    }
    // 构造函数, 通过一个给定数组创建一个最大堆
    // 该构造堆的过程, 时间复杂度为O(n)
    public MaxHeapO(Item arr[]) {
        int n = arr.length;
        data = (Item[]) new Comparable[n + 1];
        capacity = n;
        for (int i = 0; i < n; i++) {
            data[i + 1] = arr[i];
        }
        count = n;
        for (int i = count / 2; i >= 1; i--) {
            shiftDown(i);
        }
    }
    // 返回堆中的元素个数
    public int size() {
        return count;
    }
    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty() {
        return count == 0;
    }
    // 像最大堆中插入一个新的元素 item
    public void insert(Item item) {
        assert capacity - count >= 1;
        data[count + 1] = item;
        count++;
        shiftUp(count);
    }
    // 从最大堆中取出堆顶元素, 即堆中所存储的最大数据
    public Item extractMax() {
        assert count >= 1;
        Item ret = data[1];
        swap(1, count);
        count--;
        shiftDown(1);
        return ret;
    }
    // 获取最大堆中的堆顶元素
    public Item getMax() {
        assert (count > 0);
        return data[1];
    }
    // 交换堆中索引为i和j的两个元素
    private void swap(int i, int j) {
        Item t = data[i];
        data[i] = data[j];
        data[j] = t;
    }
    //********************
    //* 最大堆核心辅助函数
    //********************
    private void shiftUp(int k) {
        Item e = data[k];
        while (k > 1 && data[k / 2].compareTo(e) < 0) {
            //swap(k, k/2);
            data[k] = data[k / 2];
            k /= 2;
        }
        data[k] = e;
    }
    private void shiftDown(int k) {
        Item e = data[k];
        while (2 * k <= count) {
            int j = 2 * k; // 在此轮循环中,data[k]和data[j]交换位置
            if (j + 1 <= count && data[j + 1].compareTo(data[j]) > 0) {
                j++;
            }
            // data[j] 是 data[2*k]和data[2*k+1]中的最大值
            if (e.compareTo(data[j]) >= 0) {
                break;
            }
            //swap(k, j);
            data[k] = data[j];
            k = j;
        }
        data[k] = e;
    }
     测试 MaxHeapO
    //public static void main(String[] args) {
    //    MaxHeapO<Integer> maxHeap = new MaxHeapO<>(100);
    //    int N = 100; // 堆中元素个数
    //    int M = 100; // 堆中元素取值范围[0, M)
    //    for (int i = 0; i < N; i++) {
    //        maxHeap.insert(new Integer((int) (Math.random() * M)));
    //    }
    //    Integer[] arr = new Integer[N];
    //    // 将maxheap中的数据逐渐使用extractMax取出来
    //    // 取出来的顺序应该是按照从大到小的顺序取出来的
    //    for (int i = 0; i < N; i++) {
    //        arr[i] = maxHeap.extractMax();
    //        System.out.print(arr[i] + " ");
    //    }
    //    System.out.println();
    //    // 确保arr数组是从大到小排列的
    //    for (int i = 1; i < N; i++) {
    //        assert arr[i - 1] >= arr[i];
    //    }
    //}
}

原地堆排序


由于原地堆排序没有利用其他空间，所以数组下标为0的那个点也需要使用






// 不使用一个额外的最大堆, 直接在原数组上进行原地的堆排序
public static void sort(Comparable[] arr) {
    int n = arr.length;
    // 注意，此时我们的堆是从0开始索引的
    // 从(最后一个元素的索引-1)/2开始
    // 最后一个元素的索引 = n-1
    //Heapify
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        shiftDown2(arr, n, i);
    }
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        shiftDown2(arr, i, 0);
    }
}
// 交换堆中索引为i和j的两个元素
private static void swap(Object[] arr, int i, int j) {
    Object t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}
 原始的shiftDown过程
//private static void shiftDown(Comparable[] arr, int n, int k) {
//    while (2 * k + 1 < n) {
//        int j = 2 * k + 1;
//        // 在此轮循环中,data[k]和data[j]交换位置
//        if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) {
//            j += 1;
//        }
//        if (arr[k].compareTo(arr[j]) >= 0) {
//            break;
//        }
//        swap(arr, k, j);
//        k = j;
//    }
//}
// 优化的shiftDown过程, 使用赋值的方式取代不断的swap,
// 该优化思想和我们之前对插入排序进行优化的思路是一致的
private static void shiftDown2(Comparable[] arr, int n, int k) {
    Comparable e = arr[k];
    while (2 * k + 1 < n) {
        int j = 2 * k + 1;
        if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) {
            j += 1;
        }
        if (e.compareTo(arr[j]) >= 0) {
            break;
        }
        arr[k] = arr[j];
        k = j;
    }
    arr[k] = e;
}

使用堆实现多路归并排序 





 

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net 

/*
 * 堆排序是一种选择排序，时间复杂度为O(nlog<sub>2</sub>n)。
 * 
 * 堆排序的特点是：
 * 在排序过程中，将待排序数组看成是一棵完全二叉树的顺序存储结构，
 * 利用完全二叉树中父结点和子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。
 *
 * 基本思想
 * 1.将待排序数组调整为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
 * 2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置列入有序区，然后将新的无序区调整为大根堆。
 * 3.重复操作，直到无序区消失为止。
 * 初始时，整个数组为无序区。每一次交换，都是将大根堆的堆顶元素换入有序区，以保证有序区是有序的。
 */

namespace HeapSort
{
    using System;

    /// <summary>
    /// The program.
    /// </summary>
    public static class Program
    {
        /// <summary>
        /// 程序入口点。
        /// </summary>
        public static void Main()
        {
            int[] a = {1, 14, 6, 2, 8, 66, 9, 3, 0, 10, 5, 34, 76, 809, 4, 7};

            Console.WriteLine("Before Heap Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }

            Console.WriteLine("\r\n");

            Console.WriteLine("In Heap Sort:");
            HeapSort(a);
            Console.WriteLine("");

            Console.WriteLine("After Heap Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }
        }

        /// <summary>
        /// 堆排序方法。
        /// </summary>
        /// <param name="a">
        /// 待排序数组。
        /// </param>
        private static void HeapSort(int[] a)
        {
            // 建立大根堆。
            BuildMaxHeap(a);
            Console.WriteLine("Build max heap:");
            foreach (int i in a)
            {
                // 打印大根堆。
                Console.Write(i + " ");
            }

            Console.WriteLine("\r\nMax heap in each heap sort iteration:");
            for (int i = a.Length - 1; i > 0; i--)
            {
                // 将堆顶元素和无序区的最后一个元素交换。
                Swap(ref a[0], ref a[i]);

                // 将新的无序区调整为大根堆。
                MaxHeaping(a, 0, i);

                // 打印每一次堆排序迭代后的大根堆。
                for (int j = 0; j < i; j++)
                {
                    Console.Write(a[j] + " ");
                }

                Console.WriteLine(string.Empty);
            }
        }

        /// <summary>
        /// 由底向上建堆。
        /// 由完全二叉树的性质可知，叶子结点是从index=a.Length/2开始，
        /// 所以从index=(a.Length/2)-1结点开始由底向上进行大根堆的调整。
        /// </summary>
        /// <param name="a">
        /// 待排序数组。
        /// </param>
        private static void BuildMaxHeap(int[] a)
        {
            for (int i = (a.Length / 2) - 1; i >= 0; i--)
            {
                MaxHeaping(a, i, a.Length);
            }
        }

        /// <summary>
        /// 将指定的结点调整为堆。
        /// </summary>
        /// <param name="a">
        /// 待排序数组。
        /// </param>
        /// <param name="i">
        /// 需要调整的结点。
        /// </param>
        /// <param name="heapSize">
        /// 堆的大小，也指数组中无序区的长度。
        /// </param>
        private static void MaxHeaping(int[] a, int i, int heapSize)
        {
            // 左子结点。
            int left = (2 * i) + 1;

            // 右子结点。
            int right = 2 * (i + 1);

            // 临时变量，存放大的结点值。
            int large = i;

            // 比较左子结点。
            if (left < heapSize && a[left] > a[large])
            {
                large = left;
            }

            // 比较右子结点。
            if (right < heapSize && a[right] > a[large])
            {
                large = right;
            }

            // 如有子结点大于自身就交换，使大的元素上移；并且把该大的元素调整为堆以保证堆的性质。
            if (i != large)
            {
                Swap(ref a[i], ref a[large]);
                MaxHeaping(a, large, heapSize);
            }
        }

        /// <summary>
        /// 交换两个整数的值。
        /// </summary>
        /// <param name="a">整数a。</param>
        /// <param name="b">整数b。</param>
        private static void Swap(ref int a, ref int b)
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
    }
}

// Output:
/*
Before Heap Sort:
1 14 6 2 8 66 9 3 0 10 5 34 76 809 4 7

In Heap Sort:
Build max heap:
809 14 76 7 10 66 9 3 0 8 5 34 1 6 4 2
Max heap in each heap sort iteration:
76 14 66 7 10 34 9 3 0 8 5 2 1 6 4
66 14 34 7 10 4 9 3 0 8 5 2 1 6
34 14 9 7 10 4 6 3 0 8 5 2 1
14 10 9 7 8 4 6 3 0 1 5 2
10 8 9 7 5 4 6 3 0 1 2
9 8 6 7 5 4 2 3 0 1
8 7 6 3 5 4 2 1 0
7 5 6 3 0 4 2 1
6 5 4 3 0 1 2
5 3 4 2 0 1
4 3 1 2 0
3 2 1 0
2 0 1
1 0
0

After Heap Sort:
0 1 2 3 4 5 6 7 8 9 10 14 34 66 76 809
*/