文章作者:Slyar 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。
n个关键字序列Kl,K2,…,Kn称为堆(Heap),当且仅当该序列满足如下性质(简称为堆性质):
ki≤K2i且ki≤K2i+1 或 Ki≥K2i且ki≥K2i+1(1≤i≤ n)
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 (即如果按照线性存储该树,可得到一个不下降序列或不上升序列)
SLYAR整理了一下算法,用C语言实现,带注释。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
void sift(int a[],int i,int n) /* i为根节点,n为节点总数 */
{
int child,tmp;
for (tmp=a[i];n>2*i;i=child)
{
child=2*i; /* i的左孩子为2*i,右孩子为2*i+1 */
if (child!=n-1&&a[child+1]>a[child]) /* 让child指向孩子中较大的一个 */
{
child++;
}
if (tmp<a[child]) /* 如果孩子节点大 */
{
a[i]=a[child]; /* 交换孩子节点和根节点 */
}
else break;
}
a[i]=tmp; /* 将根放在合适位置 */
}
void heapsort(int a[],int n) /* 对a[1...n]进行排序 */
{
int i,tmp;
for (i=n/2;i>=0;i--) /* 建立初始堆 */
{
sift(a,i,n);
}
for (i=n-1;i>0;i--) /* 进行n-1趟排序 */
{
tmp=a[0]; /* 交换堆顶元素和最后一个元素 */
a[0]=a[i];
a[i]=tmp;
sift(a,0,i); /* 将a[1..n-1]重建为堆 */
}
}
|
分享到:
相关推荐
堆排序 堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法
经典排序算法 - 堆排序Heap sort序 经典排序算法 - 地精排序Gnome Sort 经典排序算法 - 奇偶排序Odd-even sort 经典排序算法 - 梳排序Comb sort 经典排序算法 - 耐心排序Patience Sorting 经典排序算法 - 珠...
我刚用C#写的堆排序算法(HEAPSORT),算法简洁,质量不错,只是注释不多
堆排序(C语言实现)算法思想步骤程序 算法思想 见: 4. 选择排序—堆排序(Heap Sort) 算法导论——堆排序heapsort 步骤 1. 将n个元素建立初始堆,第一个节点放在数组下标1中,因此n个节点对应数组 a[1] ~ a[n],...
主要为大家详细介绍了PHP实现排序堆排序(Heap Sort)算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
主要介绍了PHP排序算法之堆排序(Heap Sort),结合实例形式详细分析了堆排序的原理、实现方法及相关使用注意事项,需要的朋友可以参考下
堆排序算法的java实现,采用大根堆。时间复杂度为O(nlogn).
按照算法导论上的伪代码写出的堆数据结构,实现的是最大堆的堆排序
堆,归并,快速,插入,heap sort等排序算法的所有实现。一个很好的学习机会
以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下
C语言中常见的排序算法包括归并排序、选择排序、直接插入排序、希尔排序、冒泡排序、快速排序、堆排序以及顺序查找和二分查找。这些排序算法各有特点,在不同情况下有着不同的应用场景和性能表现。 归并排序(Merge...
java十大排序算法实现 1. 冒泡排序(Bubble Sort) 2. 选择排序(Selection ...6. 堆排序(Heap Sort) 7. 计数排序(Counting Sort) 8. 桶排序(Bucket Sort) 9. 基数排序(Radix Sort) 10. 希尔排序(Shell Sort)
排序算法 - 快速排序(Insert Sort) - 希尔排序(Shell Sort) - 冒泡排序(Bubble Sort) - 快速排序(Quick Sort) ...- 堆排序(Heap Sort) - 归并排序(Merge Sort) - 箱排序(Bin Sort) - 基数排序(Radix Sort)
堆排序(Heapsort)是指利用堆这种数据结构(后面的【图解数据结构】内容会讲解分析)所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的...
各种排序算法,包括希尔算法,快速排序,堆排序-A variety of sorting algorithms, including the Hill algorithm, quick sort, heap sort
堆排序(Heap Sort) 计数排序(Counting Sort) 基数排序(Radix Sort) 桶排序(Bucket Sort) 深度优先搜索(Depth-First Search, DFS) 广度优先搜索(Breadth-First Search, BFS) 二分查找(Binary Search) ...
《算法设计技巧与分析》...•Design and implement Heapsort1 algorithm based on minmal heap to sort an array in nonascending order; •Implement algorithm 4.6 and 4.7, test the implementation on example 4.4