信息
- 外文名
- 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<sub>2</sub>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 */
收藏数
42,057
精华内容
16,822
-
SCUT-HEAD-Dataset-Release
-
FastDFS 分布式文件系统部署
-
php值转换之strval()、intval()、floatval()、bool
-
NFS 实现高可用(DRBD + heartbeat)
-
2015年上半年 数据库系统工程师 上午试卷 综合知识 软考真题【含答案和答案解析】
-
使用内置传感器的LED进行LED热阻和TIM评估的研究
-
python数据分析之Pandas数据结构和操作
-
2017年上半年 信息系统管理工程师 上午试卷 综合知识 软考真题【含答案和答案解析】
-
物联网之mqtt实现(emqx+springboot+mqtt附源码)
-
需求分析与建模最佳实践
-
区块链应用开发实战(Go语言方向)
-
易意-源码
-
详解敏捷测试
-
朱老师c++课程第3部分-3.5STL的其他容器讲解
-
XSS渗透测试
-
Unity 热更新技术-ILRuntime
-
电商PC前后端分离项目Spring Boot后台实战第一期
-
jquery使用serialize()出现中文乱码怎么办
-
APPKIT打造稳定、灵活、高效的运营配置平台
-
arwin:Visual C ++项目中的arwin-源码