当前位置: 代码迷 >> 综合 >> 堆排序 oj
  详细解决方案

堆排序 oj

热度:64   发布时间:2024-01-14 23:02:42.0

堆排序

// 百度百科
堆排序(Heapsort)是指利用堆积树(堆)这种 数据结构所设计的一种 排序算法,它是选择排序的一种。可以利用 数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是 完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即 A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。
中文名
堆排序
外文名
Heapsort
类    别
排序算法
发明人
罗伯特·弗洛伊德
起源于
罗伯特·弗洛伊德

目录

  1. 1起源
  2. 2堆
  3. ?定义
  4. ?高度
  5. 3简介
  6. ?注意
  1. ?特点
  2. 4算法分析
  3. ?平均性能
  4. ?其他性能
  5. 5示例代码
  6. ?C语言
  1. ?C++
  2. ?Java
  3. ?Python
  4. ?C#
  5. ?JavaScript
  6. ?Pascal代码

起源

编辑
[1] 1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授 罗伯特·弗洛伊德(Robert W.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了著名的堆排序算法( Heap Sort )

堆

编辑

定义

n个关键字序列Kl,K2,…,Kn称为(Heap),当且仅当该序列满足如下性质(简称为堆性质):
(1)ki<=k(2i)且ki<=k(2i+1)(1≤i≤ n/2),当然,这是小根堆,大根堆则换成>=号。//k(i)相当于 二叉树的非 叶子结点,K(2i)则是左子节点,k(2i+1)是右子节点
若将此序列所存储的向量R[1..n]看做是一棵 完全二叉树的 存储结构,则堆实质上是满足如下性质的完全二叉树:
树中任一非叶子结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
【例】关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1)和(2),故它们均是堆,其对应的 完全二叉树分别如小根堆示例和大根堆示例所示。
大根堆和小根堆:根结点(亦称为堆顶)的 关键字是堆里所有结点关键字中最小者的堆称为小根堆,又称 最小堆。根结点(亦称为堆顶)的 关键字是堆里所有结点关键字中最大者,称为大根堆,又称最大堆。注意:①堆中任一子树亦是堆。②以上讨论的堆实际上是 二叉堆(Binary Heap),类似地可定义k叉堆。

高度

堆可以被看成是一棵树,结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目;定义堆的高度为树根的高度。我们将看到,堆结构上的一些基本操作的运行时间至多是与树的高度成正比,为O(lgn)。

简介

编辑
堆排序利用了大根堆(或小根堆)堆顶记录的 关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
(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)大根堆排序算法的基本操作:
①建堆,建堆是不断调整堆的过程,从len/2处开始调整,一直到第一个节点,此处len是堆中元素的个数。建堆的过程是线性的过程,从len/2到0处一直调用调整堆的过程,相当于o(h1)+o(h2)…+o(hlen/2) 其中h表示节点的深度,len/2表示节点的个数,这是一个求和的过程,结果是线性的O(n)。
②调整堆:调整堆在构建堆的过程中会用到,而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i),选出三者最大(或者最小)者,如果最大(小)值不是节点i而是它的一个孩子节点,那边交互节点i和该节点,然后再调用调整堆过程,这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系,是lgn的操作,因为是沿着深度方向进行调整的。
③堆排序:堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换),将前面len-1个节点继续进行堆调整的过程,然后再将根节点取出,这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)(调用一次);调整堆的时间复杂度是lgn,调用了n-1次,所以堆排序的时间复杂度是O(nlgn) [2]

注意

①只需做n-1趟排序,选出较大的n-1个 关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接 选择排序相反:在任何时刻堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止

特点

堆排序(HeapSort)是一树形 选择排序。堆排序的特点是:在排序过程中,将R[l..n]看成是一棵 完全二叉树的 顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构),在当前无序区中选择 关键字最大(或最小)的记录

算法分析

编辑
堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。

平均性能

O(N*logN)。

其他性能

由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序,辅助空间为O(1).
它是 不稳定的排序方法。(排序的稳定性是指如果在排序的序列中,存在前后相同的两个元素的话,排序前 和排序后他们的相对位置不发生变化)

示例代码

编辑

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
//array是待调整的堆数组,i是待调整的数组元素的位置,nlength是数组的长度
//本函数功能是:根据数组array构建大根堆
void  HeapAdjust( int  array[], int  i, int  nLength)
{
     int  nChild;
     int  nTemp;
     for (;2*i+1<nLength;i=nChild)
     {
         //子结点的位置=2*(父结点位置)+1
         nChild=2*i+1;
         //得到子结点中较大的结点
         if (nChild<nLength-1&&array[nChild+1]>array[nChild])++nChild;
         //如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点
         if (array[i]<array[nChild])
         {
             nTemp=array[i];
             array[i]=array[nChild];
             array[nChild]=nTemp; 
         }
         else  break ;  //否则退出循环
     }
}
//堆排序算法
void  HeapSort( int  array[], int  length)
{
     int  i;
     //调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素
     //length/2-1是最后一个非叶节点,此处"/"为整除
     for (i=length/2-1;i>=0;--i)
     HeapAdjust(array,i,length);
     //从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素
     for (i=length-1;i>0;--i)
     {
         //把第一个元素和当前的最后一个元素交换,
         //保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
         array[i]=array[0]^array[i];
         array[0]=array[0]^array[i];
         array[i]=array[0]^array[i];
         //不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值
         HeapAdjust(array,0,i);
     }
}
int  main()
{
     int  i;
     int  num[]={9,8,7,6,5,4,3,2,1,0};
     HeapSort(num, sizeof (num)/ sizeof ( int ));
     for (i=0;i< sizeof (num)/ sizeof ( int );i++)
     {
         printf ( "%d " ,num[i]);
     }
     printf ( "\nok\n" );
     return  0;
}

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//堆排序
//整理节点time:O(lgn)
template <typenameT>
void  MinHeapify(T*arry, int  size, int  element)
{
int  lchild=element*2+1,rchild=lchild+1; //左右子树
while (rchild<size) //子树均在范围内
{
if (arry[element]<=arry[lchild]&&arry[element]<=arry[rchild]) //如果比左右子树都小,完成整理
{
return ;
}
if (arry[lchild]<=arry[rchild]) //如果左边最小
{
swap(arry[element],arry[lchild]); //把左面的提到上面
element=lchild; //循环时整理子树
}
else //否则右面最小
{
swap(arry[element],arry[rchild]); //同理
element=rchild;
}
lchild=element*2+1;
rchild=lchild+1; //重新计算子树位置
}
if (lchild<size&&arry[lchild]<arry[element]) //只有左子树且子树小于自己
{
swap(arry[lchild],arry[element]);
}
return ;
}
//堆排序time:O(nlgn)
template <typenameT>
void  HeapSort(T*arry, int  size)
{
int  i;
for (i=size-1;i>=0;i--) //从子树开始整理树
{
MinHeapify(arry,size,i);
}
while (size>0) //拆除树
{
swap(arry[size-1],arry[0]); //将根(最小)与数组最末交换
size--; //树大小减小
MinHeapify(arry,size,0); //整理树
}
return ;
}

Java

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
public  class  HeapSort{
private  static  int [] sort= new  int []{ 1 , 0 , 10 , 20 , 3 , 5 , 6 , 4 , 9 , 8 , 12 ,
17 , 34 , 11 };
public  static  void  main(String[] args){
buildMaxHeapify(sort);
heapSort(sort);
print(sort);
}
private  static  void  buildMaxHeapify( int [] data){
//没有子节点的才需要创建最大堆,从最后一个的父节点开始
int  startIndex=getParentIndex(data.length- 1 );
//从尾端开始创建最大堆,每次都是正确的堆
for ( int  i=startIndex;i>= 0 ;i--){
maxHeapify(data,data.length,i);
}
}
/**
*创建最大堆
*
*@paramdata
*@paramheapSize需要创建最大堆的大小,一般在sort的时候用到,因为最多值放在末尾,末尾就不再归入最大堆了
*@paramindex当前需要创建最大堆的位置
*/
private  static  void  maxHeapify( int [] data, int  heapSize, int  index){
//当前点与左右子节点比较
int  left=getChildLeftIndex(index);
int  right=getChildRightIndex(index);
int  largest=index;
if (left<heapSize&&data[index]<data[left]){
largest=left;
}
if (right<heapSize&&data[largest]<data[right]){
largest=right;
}
//得到最大值后可能需要交换,如果交换了,其子节点可能就不是最大堆了,需要重新调整
if (largest!=index){
int  temp=data[index];
data[index]=data[largest];
data[largest]=temp;
maxHeapify(data,heapSize,largest);
}
}
/**
*排序,最大值放在末尾,data虽然是最大堆,在排序后就成了递增的
*
*@paramdata
*/
private  static  void  heapSort( int [] data){
//末尾与头交换,交换后调整最大堆
for ( int  i=data.length- 1 ;i> 0 ;i--){
int  temp=data[ 0 ];
data[ 0 ]=data[i];
data[i]=temp;
maxHeapify(data,i, 0 );
}
}
/**
*父节点位置
*
*@paramcurrent
*@return
*/
private  static  int  getParentIndex( int  current){
return (current- 1 )>> 1 ;
}
/**
*左子节点position注意括号,加法优先级更高
*
*@paramcurrent
*@return
*/
private  static  int  getChildLeftIndex( int  current){
return (current<< 1 )+ 1 ;
}
/**
*右子节点position
*
*@paramcurrent
*@return
*/
private  static  int  getChildRightIndex( int  current){
return (current<< 1 )+ 2 ;
}
private  static  void  print( int [] data){
int  pre=- 2 ;
for ( int  i= 0 ;i<data.length;i++){
if (pre<( int )getLog(i+ 1 )){
pre=( int )getLog(i+ 1 );
System.out.println();
}
System.out.print(data[i]+ "|" );
}
}
/**
*以2为底的对数
*
*@paramparam
*@return
*/
private  static  double  getLog( double  param){
return  Math.log(param)/Math.log( 2 );
}
}

Python

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
#!/usr/bin/envpython
#-*-coding:utf-8-*-
def  heap_sort(lst):
for  startinrange(( len (lst) - 2 ) / 2 , - 1 , - 1 ):
sift_down(lst,start, len (lst) - 1 )
for  endinrange( len (lst) - 1 , 0 , - 1 ):
lst[ 0 ],lst[end] = lst[end],lst[ 0 ]
sift_down(lst, 0 ,end - 1 )
return  lst
def  sift_down(lst,start,end):
root = start
while  True :
child = 2 * root + 1
if  child>end:
break
if  child + 1 < = end  and  lst[child]<lst[child + 1 ]:
child + = 1
if  lst[root]<lst[child]:
lst[root],lst[child] = lst[child],lst[root]
root = child
else :
break
def  main():
l = [ 9 , 2 , 1 , 7 , 6 , 8 , 5 , 3 , 4 ]
heap_sort(l)
if__name__ = = "__main__" :
main()

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
///<summary>
///构建堆
///</summary>
static  void  HeapAdjust(List< int > list, int  parent, int  length)
{
int  temp=list[parent];
int  child=2*parent+1;
while (child<length)
{
if (child+1<length&&list[child]<list[child+1])child++;
if (temp>=list[child])
break ;
list[parent]=list[child];
parent=child;
child=2*parent+1;
}
list[parent]=temp;
}
///<summary>
///堆排序
///</summary>
public  static  List< int > HeapSort(List< int > list, int  top)
{
List< int > topNode= new  List< int >();
for ( int  i=list.Count/2-1;i>=0;i--)
{
HeapAdjust(list,i,list.Count);
}
for ( int  i=list.Count-1;i>=list.Count-top;i--)
{
int  temp=list[0];
list[0]=list[i];
list[i]=temp;
topNode.Add(temp);
HeapAdjust(list,0,i);
}
return  topNode;
}

JavaScript

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
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
*AuthorJenaszhang
*/
Array.prototype.buildMaxHeap= function (){
for ( var  i=Math.floor( this .length/2)-1;i>=0;i--){
this .heapAdjust(i, this .length);
}
};
Array.prototype.swap= function (i,j){
var  tmp= this [i];
this [i]= this [j];
this [j]=tmp;
};
Array.prototype.heapSort= function (){
this .buildMaxHeap();
for (vari= this .length-1;i>0;i--){
this .swap(0,i);
this .heapAdjust(0,i);
}
return  this ;
};
Array.prototype.heapAdjust= function (i,j){
var  largest=i;
var  left=2*i+1;
var  right=2*i+2;
if (left<j&& this [largest]< this [left]){
largest=left;
}
if (right<j&& this [largest]< this [right]){
largest=right;
}
if (largest!=i){
this .swap(i,largest);
this .heapAdjust(largest,j);
}
};
var  a= new  Array();
[].push.apply(a,[2,3,89,57,23,72,43,105]);
console.log(a.heapSort());

Pascal代码

示例1:
const max=100000;
var
a:array[0..max] of longint;
n,i,tot,t:longint;
procedure down(i:longint);
var j,t:longint;
begin
while i<=tot shr 1 do
begin
j:=2*i;
if (j<tot) and (a[j+1]<a[j]) then inc(j);
if a[i]>a[j] then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
i:=j;
end
else break;
end;
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
tot:=n;
for i:=n shr 1 downto 1 do down(i);
for i:=1 to n do
begin
t:=a[1]; a[1]:=a[tot]; a[tot]:=t;
dec(tot);
down(1);
end;
for i:=n downto 1 do write(a[i],' ');
end.
示例2:
const max=100000;
var
a:array[0..max] of longint;
n,i,tot,t:longint;
procedure down(i:longint);
var j,t:longint;
begin
while i<=tot shr 1 do
begin
j:=2*i;
if (j<tot) and (a[j+1]<a[j]) then inc(j);
if a[i]>a[j] then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
i:=j;
end
else break;
end;
end;
procedure up(i:longint);
var j,t:longint;
begin
j:=i;
while (j>1) and (a[j]<a[j shr 1]) do
begin
t:=a[j];
a[j]:=a[j shr 1];
a[j shr 1]:=t;
j:=j shr 1;
end;
end;
begin
readln(n);
for i:=1 to n do
begin
read(a[i]);
up(i);
end;
tot:=n;
for i:=1 to n do
begin
t:=a[1]; a[1]:=a[tot]; a[tot]:=t;
dec(tot);
down(1);
end;
for i:=n downto 1 do write(a[i],' ');
end.
  相关解决方案