什么是堆排序
答案:4 悬赏:80
解决时间 2021-10-25 12:11
- 提问者网友:美人性情
- 2021-10-24 12:23
什么是堆排序
最佳答案
- 二级知识专家网友:长青诗
- 2021-10-24 13:32
"堆排序目录[隐藏]
起源
定义
特点
堆排序与直接选择排序的区别
堆排序
堆排序算法(C++描述)
Heapify函数思想方法
堆排序(Pascal/Delphi描述)
BuildHeap的实现
算法分析
堆排序
Pascal中的较简单实现
堆排序的JAVA实现 起源
定义
特点
堆排序与直接选择排序的区别
堆排序
堆排序算法(C++描述)
Heapify函数思想方法
堆排序(Pascal/Delphi描述)
BuildHeap的实现算法分析堆排序Pascal中的较简单实现堆排序的JAVA实现
[编辑本段]起源
1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了著名的堆排序算法( Heap Sort )
[编辑本段]定义
n个关键字序列Kl,K2,…,Kn称为(Heap),当且仅当该序列满足如下性质(简称为堆性质):
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n)
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 (即如果按照线性存储该树,可得到一个不下降序列或不上升序列)
【例】关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1)和(2),故它们均是堆,其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
大根堆和小根堆根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆,又称最小堆. 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆又称最大堆. 注意: ①堆中任一子树亦是堆. ②以上讨论的堆实际上是二叉堆(Binary Heap),类似地可定义k叉堆.
[编辑本段]特点
堆排序(HeapSort)是一树形选择排序。堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构),在当前无序区中选择关键字最大(或最小)的记录。
[编辑本段]堆排序与直接选择排序的区别
直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果,可减少比较次数。
[编辑本段]堆排序
堆排序利用了大根堆堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
(1)用大根堆排序的基本思想
① 先将初始文件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]调整为堆。
……
直到无序区只有一个元素为止。
(2)大根堆排序算法的基本操作:
① 初始化操作:将R[1..n]构造为初始堆;
② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
注意:
①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
[编辑本段]堆排序算法(C++描述)
void HeapSort(SeqIAst R)
{ //对R[1..n]进行堆排序,不妨用R[0]做暂存单元
int i;
BuildHeap(R); //将R[1-n]建成初始堆
for(i=n;i>1;i--)
{
//对当前无序区R[1..i]进行堆排序,共做n-1趟。
R[0]=R[1];
R[1]=R;
R=R[0];//将堆顶和堆中最后一个记录交换
Heapify(R,1,i-1);
//将R[1..i-1]重新调整为堆,仅有R[1] 可能违反堆性质
} //endfor
}
//HeapSort
因为构造初始堆必须使用到调整堆的操作,先讨论Heapify的实现。
[编辑本段]Heapify函数思想方法
每趟排序开始前R[l..i]是以R[1]为根的堆,在R[1]与R交换后,新的无序区R[1..i-1]中只有R[1]的值发生了变化,故除R[1]可能违反堆性质外,其余任何结点为根的子树均是堆。因此,当被调整区间是R[low..high]时,只须调整以R[low]为根的树即可。
""筛选法""调整堆
R[low]的左、右子树(若存在)均已是堆,这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字,则R[low]未违反堆[性质,以R[low]为根的树已是堆,无须调整;否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换,即R[low]与R[large](R[large].key=max(R[2low].key,R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质,同样由于该结点的两棵子树(若存在)仍然是堆,故可重复上述的调整过程,对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足性质,或者该结点已是叶子为止。上述过程就象过筛子一样,把较小的关键字逐层筛下去,而将较大的关键字逐层选上来。因此,有人将此方法称为""筛选法""。
算法实例:
#include <stdio.h>
#include<stdlib.h>
inline int LEFt(int i);
inline int RIGHt(int i);
inline int PATENT(int i);
void MAX_HEAPIFY(int A[],int heap_size,int i);
void BUILD_MAX_HEAP(int A[],int heap_size);
void HEAPSORT(int A[],int heap_size);
void output(int A[],int size);
int main()
{
FILE *fin;
int m,size,i;
fin = fopen(""array.in"",""r"");
int* a;
fscanf(fin,"" %d"",&size);
a = (int *)malloc(size + 1);
a[0]=size;
for(i = 1;i <= size; i++ )
{
fscanf(fin,"" %d"",&m);
a = m;
}
HEAPSORT(a,a[0]);
printf(""$$$$$$$$$$The Result$$$$$$$$\n"");
output(a,a[0]);
free(a);
return 0;
}
inline int LEFt(int i)
{
return 2 * i;
}
inline int RIGHt(int i)
{
return 2 * i + 1;
}
inline int PARENT(int i)
{
return i / 2;
}
void MAX_HEAPIFY(int A[],int heap_size,int i)
{
int temp,largest,l,r;
largest = i;
l = LEFt(i);
r = RIGHt(i);
if ((l <= heap_size) && (A[l] > A[largest])) largest = l;
if ((r <= heap_size) && (A[r] > A[largest])) largest = r;
if (largest != i)
{
temp = A[largest];
A[largest] = A;
A= temp;
MAX_HEAPIFY(A,heap_size,largest);
}
}
void BUILD_MAX_HEAP(int A[],int heap_size)
{
int i;
for (i = heap_size / 2;i >= 1;i--) MAX_HEAPIFY(A,heap_size,i);
}
void HEAPSORT(int A[],int heap_size)
{
int i;
BUILD_MAX_HEAP(A,heap_size);
for (i = heap_size;i >= 2; i--)
{
int temp;
temp = A[1];
A[1] = A;
A = temp;
MAX_HEAPIFY(A,i-1,1);
}
}
void output(int A[],int size)
{
int i = 1;
FILE *out = fopen(""result.in"",""w+"");
for (; i <= size; i++)
{
printf(""%d "",A);
fprintf(out,""%d "",A);
}
printf(""\n"");
}
[编辑本段]堆排序(Pascal/Delphi描述)
Const
FI = 'Heap.In' ;
FO = 'Heap.Out' ;
MaxSize = 10000 ;
Type
TIndex = Longint ;
TDat = Array [ 0 .. MaxSize ] Of TIndex ;
Var
N , M : TIndex ;
D : TDat ;
Procedure Swap ( A, B : TIndex ) ;
Var
Tmp : TIndex ;
Begin
Tmp := D [ A ] ;
D [ A ] := D [ B ] ;
D [ B ] := Tmp ;
End ;
Procedure DownSift ( Node : TIndex ) ;
Var
LSon , RSon : TIndex ;
Father : TIndex ;
Change : Boolean ;
Begin
Repeat
Change := False ;
If Node Shl 1 > N Then
Exit ;
LSon := Node Shl 1 ;
RSon := LSon + 1 ;
Father := Node ;
If ( LSon <= N ) And ( D [ Father ] < D [ LSon ] ) Then
Father := LSon ;
If ( RSon <= N ) And ( D [ Father ] < D [ RSon ] ) Then
Father := RSon ;
If ( Father <> Node ) Then
Begin
Swap ( Father , Node ) ;
Node := Father ;
Change := True ;
End ;
Until Not Change ;
End ;
Procedure HeapReset ;
Var
I : TIndex ;
Begin
For I := ( N Shr 1 ) DownTo 1 Do
DownSift ( I ) ;
End ;
Procedure Init ;
Var
I : TIndex ;
Begin
FillChar ( D , SizeOf ( D ) , 0 ) ;
Readln ( N ) ;
For I := 1 To N Do
Read ( D [ I ] ) ;
End ;
Procedure Main ;
Var
I : TIndex ;
Begin
M := N ;
HeapReset ;
For I := M DownTo 2 Do
Begin
Swap ( 1 , N ) ;
Dec ( N ) ;
DownSift ( 1 ) ;
End ;
End ;
Procedure Final ;
Var
I : TIndex ;
Begin
For I := 1 To M Do
Write ( D [ I ] , ' ' ) ;
End ;
Begin
Assign ( Input , FI ) ;
Assign ( Output , FO ) ;
Reset ( Input ) ;
Rewrite ( Output ) ;
Init ;
Main ;
Final ;
Close ( Input ) ;
Close ( Output ) ;
End .
[编辑本段]BuildHeap的实现
要将初始文件R[l..n]调整为一个大根堆,就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。
显然只有一个结点的树是堆,而在完全二叉树中,所有序号大于n/2的结点都是叶子,因此以这些结点为根的子树均已是堆。这样,我们只需依次将以序号为n/2,…,1的结点作为根的子树都调整为堆即可。
[编辑本段]算法分析
堆[排序的时间,主要由建立初始]堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlog2n)。堆序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序,辅助空间为O(1),
它是不稳定的排序方法。
[编辑本段]堆排序
1.定义
树形选择排序(锦标赛排序),1964年威洛姆斯(J.Willioms)提出了进一步改正的排序方法,即堆排序(heap sort)。
堆是n个元素的有限序列{ K1,K2,…,Kn },它当且仅当满足如下关系:
这是一个上小、底大的堆。若是一个上大、底小的堆,只需把""<= ”改为"">= ”即可。堆是一种数据元素之间的逻辑关系,常用向量做存储结构。对于满二叉树,当对它的结点由上而下,自左至右编号之后,编号为 i 的结点是编号为 2i 和 2i+1 结点的双亲。反过来讲,结点 2i 是结点 i 的左孩子,结点 2i+1 是结点 i 的右孩子。图 9.7 表示完全二叉树和它在向量中的存储状态。结点编号对应向量中的下标号。
用堆的概念分析向量中的数据,它显然满足(上小、底大)堆的关系。不难看出满足堆的逻辑关系的一组数据,可画成二叉树的形状,并且它是一棵完全二叉树树形。因此,也可借助完全二叉树来描述堆的概念。若完全二叉树中任一非叶子结点的值小于等于(或大于等于)其左、右孩子结点的值,则从根结点开始按结点编号排列所得的结点序列就是一个堆。在图 9.8 中 (a) 、 (c) 是堆, (b) 、 (d) 不是堆。
2.堆排序的算法思想
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
(1)用大根堆排序的基本思想
① 先将初始文件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]调整为堆。
……
直到无序区只有一个元素为止。
(2)大根堆排序算法的基本操作:
① 初始化操作:将R[1..n]构造为初始堆;
② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
注意:
①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻,堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
3.具体算法
template<class T>
heapsort(T r[],int n) //n为文件的实际记录数,r[0]没有使用
{ int i,m;node x;
for(i=/2;i>=1;i--)heappass(r,i,n); //初建堆
//以下for语句为输出堆顶元素、调整堆操作
for(m=n-1;m>=1;m--)//逻辑堆尾下标m不断变小
{ cout<<r[1].key<<"" "";
x=r[1];r[1]=r[m+1];r[m+1]=x; //堆顶与堆尾元素对换
heappass(r,1,m);//恢复堆
}
cout<<r[1].key<<endl;
} //heapsort
4.算法时间复杂度
堆排序中 heap 算法的时间复杂度与堆所对应的完全二叉树的树高度 log2n 相关。而 heapsort 中对 heap 的调用数量级为n,所以堆排序的整个时间复杂度为O(nlog2n) 。并且堆排序是不稳定的。
[编辑本段]Pascal中的较简单实现
var
i,j,k,n:integer;
a:array[0..100] of integer;
procedure swap(var a,b:integer);
var t:integer;
begin
t:=a;
a:=b;
b:=t;
end;
procedure heapsort(i,m:integer);
begin
while i*2<=m do
begin
i:=i*2;
if (i<m) and (a<a) then inc(i);
if a>a then swap(a,a)
else break;
end;
end;
begin
randomize;
writeln('Input N');
readln(n);
for i:=1 to n do
a:=random(100)+1;
for i:=1 to n do
write(a:5);
writeln;
for i:=n div 2 downto 1 do
heapsort(i,n);
for i:=n downto 2 do
begin
swap(a,a[1]);
heapsort(1,i-1);
end;
for i:=1 to n do
write(a:5);
readln;
end.
[编辑本段]堆排序的JAVA实现
public class Test {
public static int[] Heap = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; // 预设数据数组
public static void main(String args[]) {
int i; // 循环计数变量
int Index = Heap.length; // 数据索引变量
System.out.print(""排序前: "");
for (i = 1; i < Index - 1; i++)
System.out.printf(""%3s"", Heap);
System.out.println("""");
HeapSort(Index - 2); // 堆排序
System.out.print(""排序后: "");
for (i = 1; i < Index - 1; i++)
System.out.printf(""%3s"", Heap);
System.out.println("""");
}
public static void CreateHeap(int Root, int Index) {
int i, j; // 循环计数变量
int Temp; // 暂存变量
int Finish; // 判断堆是否建立完成
j = 2 * Root; // 子节点的Index
Temp = Heap[Root]; // 暂存Heap的Root 值
Finish = 0; // 预设堆建立尚未完成
while (j <= Index && Finish == 0) {
if (j < Index) // 找最大的子节点
if (Heap[j] < Heap[j + 1])
j++;
if (Temp >= Heap[j])
Finish = 1; // 堆建立完成
else {
Heap[j / 2] = Heap[j]; // 父节点 = 目前节点
j = 2 * j;
}
}
Heap[j / 2] = Temp; // 父节点 = Root值
}
public static void HeapSort(int Index) {
int i, j, Temp;
// 将二叉树转成Heap
for (i = (Index / 2); i >= 1; i--)
CreateHeap(i, Index);
// 开始进行堆排序
for (i = Index - 1; i >= 1; i--) {
Temp = Heap; // Heap的Root值和最后一个值交换
Heap = Heap[1];
Heap[1] = Temp;
CreateHeap(1, i); // 对其余数值重建堆
System.out.print(""排序中: "");
for (j = 1; j <= Index; j++)
System.out.printf(""%3s"",Heap[j]);
System.out.println("""");
}
}
}
"
起源
定义
特点
堆排序与直接选择排序的区别
堆排序
堆排序算法(C++描述)
Heapify函数思想方法
堆排序(Pascal/Delphi描述)
BuildHeap的实现
算法分析
堆排序
Pascal中的较简单实现
堆排序的JAVA实现 起源
定义
特点
堆排序与直接选择排序的区别
堆排序
堆排序算法(C++描述)
Heapify函数思想方法
堆排序(Pascal/Delphi描述)
BuildHeap的实现算法分析堆排序Pascal中的较简单实现堆排序的JAVA实现
[编辑本段]起源
1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了著名的堆排序算法( Heap Sort )
[编辑本段]定义
n个关键字序列Kl,K2,…,Kn称为(Heap),当且仅当该序列满足如下性质(简称为堆性质):
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n)
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 (即如果按照线性存储该树,可得到一个不下降序列或不上升序列)
【例】关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1)和(2),故它们均是堆,其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
大根堆和小根堆根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆,又称最小堆. 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆又称最大堆. 注意: ①堆中任一子树亦是堆. ②以上讨论的堆实际上是二叉堆(Binary Heap),类似地可定义k叉堆.
[编辑本段]特点
堆排序(HeapSort)是一树形选择排序。堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构),在当前无序区中选择关键字最大(或最小)的记录。
[编辑本段]堆排序与直接选择排序的区别
直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果,可减少比较次数。
[编辑本段]堆排序
堆排序利用了大根堆堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
(1)用大根堆排序的基本思想
① 先将初始文件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]调整为堆。
……
直到无序区只有一个元素为止。
(2)大根堆排序算法的基本操作:
① 初始化操作:将R[1..n]构造为初始堆;
② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
注意:
①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
[编辑本段]堆排序算法(C++描述)
void HeapSort(SeqIAst R)
{ //对R[1..n]进行堆排序,不妨用R[0]做暂存单元
int i;
BuildHeap(R); //将R[1-n]建成初始堆
for(i=n;i>1;i--)
{
//对当前无序区R[1..i]进行堆排序,共做n-1趟。
R[0]=R[1];
R[1]=R;
R=R[0];//将堆顶和堆中最后一个记录交换
Heapify(R,1,i-1);
//将R[1..i-1]重新调整为堆,仅有R[1] 可能违反堆性质
} //endfor
}
//HeapSort
因为构造初始堆必须使用到调整堆的操作,先讨论Heapify的实现。
[编辑本段]Heapify函数思想方法
每趟排序开始前R[l..i]是以R[1]为根的堆,在R[1]与R交换后,新的无序区R[1..i-1]中只有R[1]的值发生了变化,故除R[1]可能违反堆性质外,其余任何结点为根的子树均是堆。因此,当被调整区间是R[low..high]时,只须调整以R[low]为根的树即可。
""筛选法""调整堆
R[low]的左、右子树(若存在)均已是堆,这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字,则R[low]未违反堆[性质,以R[low]为根的树已是堆,无须调整;否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换,即R[low]与R[large](R[large].key=max(R[2low].key,R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质,同样由于该结点的两棵子树(若存在)仍然是堆,故可重复上述的调整过程,对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足性质,或者该结点已是叶子为止。上述过程就象过筛子一样,把较小的关键字逐层筛下去,而将较大的关键字逐层选上来。因此,有人将此方法称为""筛选法""。
算法实例:
#include <stdio.h>
#include<stdlib.h>
inline int LEFt(int i);
inline int RIGHt(int i);
inline int PATENT(int i);
void MAX_HEAPIFY(int A[],int heap_size,int i);
void BUILD_MAX_HEAP(int A[],int heap_size);
void HEAPSORT(int A[],int heap_size);
void output(int A[],int size);
int main()
{
FILE *fin;
int m,size,i;
fin = fopen(""array.in"",""r"");
int* a;
fscanf(fin,"" %d"",&size);
a = (int *)malloc(size + 1);
a[0]=size;
for(i = 1;i <= size; i++ )
{
fscanf(fin,"" %d"",&m);
a = m;
}
HEAPSORT(a,a[0]);
printf(""$$$$$$$$$$The Result$$$$$$$$\n"");
output(a,a[0]);
free(a);
return 0;
}
inline int LEFt(int i)
{
return 2 * i;
}
inline int RIGHt(int i)
{
return 2 * i + 1;
}
inline int PARENT(int i)
{
return i / 2;
}
void MAX_HEAPIFY(int A[],int heap_size,int i)
{
int temp,largest,l,r;
largest = i;
l = LEFt(i);
r = RIGHt(i);
if ((l <= heap_size) && (A[l] > A[largest])) largest = l;
if ((r <= heap_size) && (A[r] > A[largest])) largest = r;
if (largest != i)
{
temp = A[largest];
A[largest] = A;
A= temp;
MAX_HEAPIFY(A,heap_size,largest);
}
}
void BUILD_MAX_HEAP(int A[],int heap_size)
{
int i;
for (i = heap_size / 2;i >= 1;i--) MAX_HEAPIFY(A,heap_size,i);
}
void HEAPSORT(int A[],int heap_size)
{
int i;
BUILD_MAX_HEAP(A,heap_size);
for (i = heap_size;i >= 2; i--)
{
int temp;
temp = A[1];
A[1] = A;
A = temp;
MAX_HEAPIFY(A,i-1,1);
}
}
void output(int A[],int size)
{
int i = 1;
FILE *out = fopen(""result.in"",""w+"");
for (; i <= size; i++)
{
printf(""%d "",A);
fprintf(out,""%d "",A);
}
printf(""\n"");
}
[编辑本段]堆排序(Pascal/Delphi描述)
Const
FI = 'Heap.In' ;
FO = 'Heap.Out' ;
MaxSize = 10000 ;
Type
TIndex = Longint ;
TDat = Array [ 0 .. MaxSize ] Of TIndex ;
Var
N , M : TIndex ;
D : TDat ;
Procedure Swap ( A, B : TIndex ) ;
Var
Tmp : TIndex ;
Begin
Tmp := D [ A ] ;
D [ A ] := D [ B ] ;
D [ B ] := Tmp ;
End ;
Procedure DownSift ( Node : TIndex ) ;
Var
LSon , RSon : TIndex ;
Father : TIndex ;
Change : Boolean ;
Begin
Repeat
Change := False ;
If Node Shl 1 > N Then
Exit ;
LSon := Node Shl 1 ;
RSon := LSon + 1 ;
Father := Node ;
If ( LSon <= N ) And ( D [ Father ] < D [ LSon ] ) Then
Father := LSon ;
If ( RSon <= N ) And ( D [ Father ] < D [ RSon ] ) Then
Father := RSon ;
If ( Father <> Node ) Then
Begin
Swap ( Father , Node ) ;
Node := Father ;
Change := True ;
End ;
Until Not Change ;
End ;
Procedure HeapReset ;
Var
I : TIndex ;
Begin
For I := ( N Shr 1 ) DownTo 1 Do
DownSift ( I ) ;
End ;
Procedure Init ;
Var
I : TIndex ;
Begin
FillChar ( D , SizeOf ( D ) , 0 ) ;
Readln ( N ) ;
For I := 1 To N Do
Read ( D [ I ] ) ;
End ;
Procedure Main ;
Var
I : TIndex ;
Begin
M := N ;
HeapReset ;
For I := M DownTo 2 Do
Begin
Swap ( 1 , N ) ;
Dec ( N ) ;
DownSift ( 1 ) ;
End ;
End ;
Procedure Final ;
Var
I : TIndex ;
Begin
For I := 1 To M Do
Write ( D [ I ] , ' ' ) ;
End ;
Begin
Assign ( Input , FI ) ;
Assign ( Output , FO ) ;
Reset ( Input ) ;
Rewrite ( Output ) ;
Init ;
Main ;
Final ;
Close ( Input ) ;
Close ( Output ) ;
End .
[编辑本段]BuildHeap的实现
要将初始文件R[l..n]调整为一个大根堆,就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。
显然只有一个结点的树是堆,而在完全二叉树中,所有序号大于n/2的结点都是叶子,因此以这些结点为根的子树均已是堆。这样,我们只需依次将以序号为n/2,…,1的结点作为根的子树都调整为堆即可。
[编辑本段]算法分析
堆[排序的时间,主要由建立初始]堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlog2n)。堆序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序,辅助空间为O(1),
它是不稳定的排序方法。
[编辑本段]堆排序
1.定义
树形选择排序(锦标赛排序),1964年威洛姆斯(J.Willioms)提出了进一步改正的排序方法,即堆排序(heap sort)。
堆是n个元素的有限序列{ K1,K2,…,Kn },它当且仅当满足如下关系:
这是一个上小、底大的堆。若是一个上大、底小的堆,只需把""<= ”改为"">= ”即可。堆是一种数据元素之间的逻辑关系,常用向量做存储结构。对于满二叉树,当对它的结点由上而下,自左至右编号之后,编号为 i 的结点是编号为 2i 和 2i+1 结点的双亲。反过来讲,结点 2i 是结点 i 的左孩子,结点 2i+1 是结点 i 的右孩子。图 9.7 表示完全二叉树和它在向量中的存储状态。结点编号对应向量中的下标号。
用堆的概念分析向量中的数据,它显然满足(上小、底大)堆的关系。不难看出满足堆的逻辑关系的一组数据,可画成二叉树的形状,并且它是一棵完全二叉树树形。因此,也可借助完全二叉树来描述堆的概念。若完全二叉树中任一非叶子结点的值小于等于(或大于等于)其左、右孩子结点的值,则从根结点开始按结点编号排列所得的结点序列就是一个堆。在图 9.8 中 (a) 、 (c) 是堆, (b) 、 (d) 不是堆。
2.堆排序的算法思想
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
(1)用大根堆排序的基本思想
① 先将初始文件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]调整为堆。
……
直到无序区只有一个元素为止。
(2)大根堆排序算法的基本操作:
① 初始化操作:将R[1..n]构造为初始堆;
② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
注意:
①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻,堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
3.具体算法
template<class T>
heapsort(T r[],int n) //n为文件的实际记录数,r[0]没有使用
{ int i,m;node x;
for(i=/2;i>=1;i--)heappass(r,i,n); //初建堆
//以下for语句为输出堆顶元素、调整堆操作
for(m=n-1;m>=1;m--)//逻辑堆尾下标m不断变小
{ cout<<r[1].key<<"" "";
x=r[1];r[1]=r[m+1];r[m+1]=x; //堆顶与堆尾元素对换
heappass(r,1,m);//恢复堆
}
cout<<r[1].key<<endl;
} //heapsort
4.算法时间复杂度
堆排序中 heap 算法的时间复杂度与堆所对应的完全二叉树的树高度 log2n 相关。而 heapsort 中对 heap 的调用数量级为n,所以堆排序的整个时间复杂度为O(nlog2n) 。并且堆排序是不稳定的。
[编辑本段]Pascal中的较简单实现
var
i,j,k,n:integer;
a:array[0..100] of integer;
procedure swap(var a,b:integer);
var t:integer;
begin
t:=a;
a:=b;
b:=t;
end;
procedure heapsort(i,m:integer);
begin
while i*2<=m do
begin
i:=i*2;
if (i<m) and (a<a) then inc(i);
if a>a then swap(a,a)
else break;
end;
end;
begin
randomize;
writeln('Input N');
readln(n);
for i:=1 to n do
a:=random(100)+1;
for i:=1 to n do
write(a:5);
writeln;
for i:=n div 2 downto 1 do
heapsort(i,n);
for i:=n downto 2 do
begin
swap(a,a[1]);
heapsort(1,i-1);
end;
for i:=1 to n do
write(a:5);
readln;
end.
[编辑本段]堆排序的JAVA实现
public class Test {
public static int[] Heap = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; // 预设数据数组
public static void main(String args[]) {
int i; // 循环计数变量
int Index = Heap.length; // 数据索引变量
System.out.print(""排序前: "");
for (i = 1; i < Index - 1; i++)
System.out.printf(""%3s"", Heap);
System.out.println("""");
HeapSort(Index - 2); // 堆排序
System.out.print(""排序后: "");
for (i = 1; i < Index - 1; i++)
System.out.printf(""%3s"", Heap);
System.out.println("""");
}
public static void CreateHeap(int Root, int Index) {
int i, j; // 循环计数变量
int Temp; // 暂存变量
int Finish; // 判断堆是否建立完成
j = 2 * Root; // 子节点的Index
Temp = Heap[Root]; // 暂存Heap的Root 值
Finish = 0; // 预设堆建立尚未完成
while (j <= Index && Finish == 0) {
if (j < Index) // 找最大的子节点
if (Heap[j] < Heap[j + 1])
j++;
if (Temp >= Heap[j])
Finish = 1; // 堆建立完成
else {
Heap[j / 2] = Heap[j]; // 父节点 = 目前节点
j = 2 * j;
}
}
Heap[j / 2] = Temp; // 父节点 = Root值
}
public static void HeapSort(int Index) {
int i, j, Temp;
// 将二叉树转成Heap
for (i = (Index / 2); i >= 1; i--)
CreateHeap(i, Index);
// 开始进行堆排序
for (i = Index - 1; i >= 1; i--) {
Temp = Heap; // Heap的Root值和最后一个值交换
Heap = Heap[1];
Heap[1] = Temp;
CreateHeap(1, i); // 对其余数值重建堆
System.out.print(""排序中: "");
for (j = 1; j <= Index; j++)
System.out.printf(""%3s"",Heap[j]);
System.out.println("""");
}
}
}
"
全部回答
- 1楼网友:愁杀梦里人
- 2021-10-24 16:41
燃气轮机是以连续流动的气体为工质带动叶轮高速旋转,将燃料的能量转变为有用功的内燃式动力机械,是一种旋转叶轮式热力发动机。
中国在公元十二世纪的南宋高宗年间就已有走马灯的记载,它是涡轮机(透平)的雏形。15世纪末,意大利人列奥纳多·达芬奇设计出烟气转动装置,其原理与走马灯相同。至17世纪中叶,透平原理在欧洲得到了较多应用。
1791年,英国人巴伯首次描述了燃气轮机的工作过程;1872年,德国人施托尔策设计了一台燃气轮机,并于1900~1904年进行了试验,但因始终未能脱开起动机独立运行而失败;1905年,法国人勒梅尔和阿芒戈制成第一台能输出功的燃气轮机,但效率太低,因而未获得实用。
1920年,德国人霍尔茨瓦特制成第一台实用的燃气轮机,其效率为13%、功率为370千瓦,按等容加热循环工作,但因等容加热循环以断续爆燃的方式加热,存在许多重大缺点而被人们放弃。
随着空气动力学的发展,人们掌握了压气机叶片中气体扩压流动的特点,解决了设计高效率轴流式压气机的问题,因而在30年代中期出现了效率达85%的轴流式压气机。与此同时,透平效率也有了提高。在高温材料方面,出现了能承受600℃以上高温的铬镍合金钢等耐热钢,因而能采用较高的燃气初温,于是等压加热循环的燃气轮机终于得到成功的应用。
1939年,在瑞士制成了四兆瓦发电用燃气轮机,效率达18%。同年,在德国制造的喷气式飞机试飞成功,从此燃气轮机进入了实用阶段,并开始迅速发展。
随着高温材料的不断进展,以及透平采用冷却叶片并不断提高冷却效果,燃气初温逐步提高,使燃气轮机效率不断提高。单机功率也不断增大,在70年代中期出现了数种100兆瓦级的燃气轮机,最高能达到130兆瓦。
与此同时,燃气轮机的应用领域不断扩大。1941年瑞士制造的第一辆燃气轮机机车通过了试验;1947年,英国制造的第一艘装备燃气轮机的舰艇下水,它以1.86兆瓦的燃气轮机作加力动力;1950年,英国制成第一辆燃气轮机汽车。此后,燃气轮机在更多的部门中获得应用。
在燃气轮机获得广泛应用的同时,还出现了燃气轮机与其他热机相结合的复合装置。最早出现的是与活塞式内燃机相结合的装置;50~60年代,出现了以自由活塞发气机与燃气轮机组成的自由活塞燃气轮机装置,但由于笨重和系统较复杂,到70年代就停止了生产。此外,还发展了柴油机燃气轮机复合装置;另有一类利用燃气轮机排气热量供热(或蒸汽)的全能量系统,可有效地节约能源,已用于多种工业生产中。
燃气轮机的工作过程是,压气机(即压缩机)连续地从大气中吸入空气并将其压缩;压缩后的空气进入燃烧室,与喷入的燃料混合后燃烧,成为高温燃气,随即流入燃气透平中膨胀作功,推动透平叶轮带着压气机叶轮一起旋转;加热后的高温燃气的作功能力显著提高,因而燃气透平在带动压气机的同时,尚有余功作为燃气轮机的输出机械功。燃气轮机由静止起动时,需用起动机带着旋转,待加速到能独立运行后,起动机才脱开。
燃气轮机的工作过程是最简单的,称为简单循环;此外,还有回热循环和复杂循环。燃气轮机的工质来自大气,最后又排至大气,是开式循环;此外,还有工质被封闭循环使用的闭式循环。燃气轮机与其他热机相结合的称为复合循环装置。
燃气初温和压气机的压缩比,是影响燃气轮机效率的两个主要因素。提高燃气初温,并相应提高压缩比,可使燃气轮机效率显著提高。70年代末,压缩比最高达到31;工业和船用燃气轮机的燃气初温最高达1200℃左右,航空燃气轮机的超过1350℃。
燃气轮机由压气机、燃烧室和燃气透平等组成。压气机有轴流式和离心式两种,轴流式压气机效率较高,适用于大流量的场合。在小流量时,轴流式压气机因后面几级叶片很短,效率低于离心式。功率为数兆瓦的燃气轮机中,有些压气机采用轴流式加一个离心式作末级,因而在达到较高效率的同时又缩短了轴向长度。
燃烧室和透平不仅工作温度高,而且还承受燃气轮机在起动和停机时,因温度剧烈变化引起的热冲击,工作条件恶劣,故它们是决定燃气轮机寿命的关键部件。为确保有足够的寿命,这两大部件中工作条件最差的零件如火焰筒和叶片等,须用镍基和钴基合金等高温材料制造,同时还须用空气冷却来降低工作温度。
对于一台燃气轮机来说,除了主要部件外还必须有完善的调节保安系统,此外还需要配备良好的附属系统和设备,包括:起动装置、燃料系统、润滑系统、空气滤清器、进气和排气消声器等。
燃气轮机有重型和轻型两类。重型的零件较为厚重,大修周期长,寿命可达10万小时以上。轻型的结构紧凑而轻,所用材料一般较好,其中以航机的结构为最紧凑、最轻,但寿命较短。
与活塞式内燃机和蒸汽动力装置相比较,燃气轮机的主要优点是小而轻。单位功率的质量,重型燃气轮机一般为2~5千克/千瓦,而航机一般低于0.2千克/千瓦。燃气轮机占地面积小,当用于车、船等运输机械时,既可节省空间,也可装备功率更大的燃气轮机以提高车、船速度。燃气轮机的主要缺点是效率不够高,在部分负荷下效率下降快,空载时的燃料消耗量高。
不同的应用部门,对燃气轮机的要求和使用状况也不相同。功率在10兆瓦以上的燃气轮机多数用于发电,而30~40兆瓦以上的几乎全部用于发电。
燃气轮机发电机组能在无外界电源的情况下迅速起动,机动性好,在电网中用它带动尖峰负荷和作为紧急备用,能较好地保障电网的安全运行,所以应用广泛。在汽车(或拖车)电站和列车电站等移动电站中,燃气轮机因其轻小,应用也很广泛。此外,还有不少利用燃气轮机的便携电源,功率最小的在10千瓦以下。
燃气轮机的未来发展趋势是提高效率、采用高温陶瓷材料、利用核能和发展燃煤技术。提高效率的关键是提高燃气初温,即改进透平叶片的冷却技术,研制能耐更高温度的高温材料。其次是提高压缩比,研制级数更少而压缩比更高的压气机。再次是提高各个部件的效率。
高温陶瓷材料能在1360℃以上的高温下工作,用它来做透平叶片和燃烧室的火焰筒等高温零件时,就能在不用空气冷却的情况下大大提高燃气初温,从而较大地提高燃气轮机效率。适于燃气轮机的高温陶瓷材料有氮化硅和碳化硅等。
按闭式循环工作的装置能利用核能,它用高温气冷反应堆作为加热器,反应堆的冷却剂(氦或氮等)同时作为压气机和透平的工质。
燃气轮机的润滑油系统(上)
燃气轮机润滑油系统是任何一台燃气轮机必备的一个重要的辅助系统。它的作用是在机组启动、正常运行以及停机过程中,向正在运行的燃气轮机发电机组的各个轴承、传动装置及其附属设备,供应数量充足的、温度和压力合适的、干净的润滑油,以确保机组安全可靠地运行,防止发生轴承烧毁、转子轴颈过热弯曲、高速齿轮法兰变形等事故。此外,部份润滑油可能从系统分流出来,成为液压油系统的油源,或经过滤后作为控制油系统的用油。润滑油资讯网4@
- 2楼网友:独行浪子会拥风
- 2021-10-24 15:22
就是使用堆结构来实现的排序算法,堆的一个特点是父节点不小于(不大于)子节点,利用这个性质,循环取根节点就可以实现排序,(取完要调整树结构,使他仍然是堆)
- 3楼网友:白昼之月
- 2021-10-24 15:05
我暂时保留我的看法!
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯