堆积排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法。堆积树是一个近似完全二叉树的结构,并同时满足堆积属性:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序的平均时间复杂度为O(nlogn),空间复杂度为O(1)。堆排序是不稳定的。
1.小根堆和大根堆
堆有小根堆和大根堆两种,如下图所示:
2.堆的存储
堆积树是一个近似完全二叉树的结构,通常用一维数组来实现,在完全二叉树中双亲结点和孩子结点之间存在如下关系:
父节点i的左子节点在位置 (2*i);
父节点i的右子节点在位置 (2*i+1);
子节点i的父节点在位置 floor(i/2)。
3.用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区;
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key;
③ 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。
4.代码实现
public class HeapSort {
private static int left(int i){
return 2*i;
}
private static int right(int i){
return 2*i + 1;
}
public static void maxHeapify(int[] data, int i, int heapSize){
int l = left(i);
int r = right(i);
int largest;
if(l < heapSize && data[l] > data[i]){
largest = l;
}else{
largest = i;
}
if(r < heapSize && data[r] > data[largest]){
largest = r;
}
if(largest != i){
swap(data,i,largest);
maxHeapify(data, largest, heapSize);
}
}
public static void buildMaxHeap(int[] data){
int heapSize = data.length;
for(int i = heapSize/2; i >= 0; i--){
maxHeapify(data, i, heapSize);
}
}
public static void heapSort(int[] data){
int heapSize = data.length;
buildMaxHeap(data);
for(int i = heapSize - 1; i > 0; i--){
swap(data,0,i);
heapSize = heapSize - 1;
maxHeapify(data, 0, heapSize);
}
}
public static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
public static void main(String[] args) {
int[] number = {49,38,65,97,76,13,27,49};
heapSort(number);
for(int i = 0; i < number.length; i++) {
System.out.print(number[i] + " ");
}
}
}
5.补充
- 堆在调整的过程中,就是一个选择的行为,每次将最大值选至树根,而选择的路径并不是所有的元素,而是由树根至树叶的路径,因而可以加快选择的过程,所以Heap排序法才会被称之为改良的选择排序法。
-
堆可用来实现优先级队列,或者说堆就是一种优先级队列。优先级队列是这样的一种数据结构,对它的访问或者删除操作只能对集合中通过指定优先级方法得出的最高优先级元素进行。
分享到:
相关推荐
堆排序 堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法
经典排序算法 - 堆排序Heap sort序 经典排序算法 - 地精排序Gnome Sort 经典排序算法 - 奇偶排序Odd-even sort 经典排序算法 - 梳排序Comb sort 经典排序算法 - 耐心排序Patience Sorting 经典排序算法 - 珠...
void heap_sort(int A[],int length) { BUILD_MAX_HEAP(A,length); int i,middle; for(i=length-1;i>0;i--) { middle=A[0]; A[0]=A[i]; A[i]=middle; heap_size--; MAX_HEAPIFY(A,0); } }
我刚用C#写的堆排序算法(HEAPSORT),算法简洁,质量不错,只是注释不多
用C++实现的 堆排序,包括恢复堆,构建初始堆
主要为大家详细介绍了PHP实现排序堆排序(Heap Sort)算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
主要介绍了PHP排序算法之堆排序(Heap Sort),结合实例形式详细分析了堆排序的原理、实现方法及相关使用注意事项,需要的朋友可以参考下
堆排序,C语言写成。 凑字数真的很难,我觉得我已经说的很清楚了。
堆排序算法的java实现,采用大根堆。时间复杂度为O(nlogn).
堆排序(Heapsort)是指利用堆这种数据结构(后面的【图解数据结构】内容会讲解分析)所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的...
C++ 堆排序
c++ code for MaxHeap Sort
排序算法 - 快速排序(Insert Sort) - 希尔排序(Shell Sort) - 冒泡排序(Bubble Sort) - 快速排序(Quick Sort) ...- 堆排序(Heap Sort) - 归并排序(Merge Sort) - 箱排序(Bin Sort) - 基数排序(Radix Sort)
堆排序(Heap Sort) 插入排序(Insertion Sort) 引入排序(Intro Sort) 迭代归并排序(Iterative Merge Sort) 归并插入排序(Merge Insertion Sort) 归并排序(Merge Sort) 最高有效数字优先的基数排序(Msd ...
堆排序是一种基于二叉堆的排序算法,它通过...本文提供了一个带有详细注释的Python实现,包括heapify函数用于维护堆的性质,以及heap_sort函数作为堆排序的主函数。示例展示了如何使用这些函数对一个整数数组进行排序。
以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下
堆排序就是把先将父节点的最大数取出,并构建最大堆,再将堆继续调整为最大堆,再次将堆顶的最大数取出,这个过程持续到剩余数只有一个时结束。堆排序(Heap-Sort
堆排序(Heap Sort):利用堆的性质进行排序,将数组构建成最大堆或最小堆,然后依次将堆顶元素与最后一个元素交换并重新调整堆,直到整个数组有序。 顺序查找(Sequential Search):逐个遍历数组元素,查找目标...