堆排序 订阅
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 展开全文
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
信息
外文名
Heapsort
发明人
罗伯特·弗洛伊德
类    别
排序算法
中文名
堆排序
起源于
罗伯特·弗洛伊德
堆排序简介
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 [1] 
收起全文
精华内容
下载资源
问答
  • 堆排序

    千次阅读 2019-11-03 11:05:57
    堆排序

    二叉堆 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;
    }

    使用堆实现多路归并排序 


     

    展开全文
  • 算法 - 堆排序(C#)

    万次阅读 多人点赞 2019-02-01 15:34:50
    * 堆排序是一种选择排序,时间复杂度为O(nlog&lt;sub&gt;2&lt;/sub&gt;n)。 * * 堆排序的特点是: * 在排序过程中,将待排序数组看成是一棵完全二叉树的顺序存储结构, * 利用完全二叉树中父...

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击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
    */

     

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 42,057
精华内容 16,822
关键字:

堆排序