Linux

C++博客 :: 首頁 :: 聯系 :: 聚合

:: 管理

11 Posts :: 14 Stories :: 1 Comments :: 0 Trackbacks

常用鏈接

留言簿(4)

我參與的團隊

隨筆分類

隨筆檔案

2011年12月 (11)

文章分類

文章檔案

2011年12月 (14)

Edit

算法

sysu_mjc
算法

搜索

閱讀排行榜

評論排行榜

heap sort (Heap 的build，排序)

堆實際上是一個數組對象，可以被視為一個完全二叉樹，有完全二叉樹的遍歷得到（算法導論第六章）

思想：
最大堆和最小堆：
本文以最大堆作為介紹，主要的函數 max_heapify 和 heap_sort 利用遞歸
max_heapify函數的主要作用是調整對的結構，是其滿足最大堆的性質（其中利用遞歸），
max_heapify（int i，int len）len參數是數組的個數，i參數是“備用根”的下標。

代碼：

#include<iostream>
2

#include<stdlib.h>
3

#include<time.h>
4

using namespace std;
5

class heap{
7

public:
8

heap()
9

{
10

a=NULL;
11

size=10;
12

heap(size);
13

}
14

heap(int size_t):size(size_t)
16

{
17

a=new int[size+1];
18

srand(time(NULL));
19

for(int i=1;i<=size;i++)
21

{
22

a[i]=rand()%1000;
23

}
24

}
25

/* heap(int *b)
27

{
28

int len=sizeof(b);
29

size=len;
30

a=new int[size+1];
31

for(int i=1;i<=size;i++)
33

{
34

a[i]=b[i-1];
35

}
36

}*/
37

~heap()
39

{
40

cout<<"Destroy

..\n";
41

delete []a;
42

a=NULL;
43

}
44

void max_heapify(int i,int len);
46

void build_heap();
47

void heap_sort();
48

void print();
51

int left(int i){return 2*i;}
53

int right(int i){return 2*i+1;}
54

int parent(int i ){return i/2;}
55

private:
56

int *a;
57

int size;
58

};
59

void heap::heap_sort()
61

{
62

int len=size;
63

int t;
64

for(int i=size;i>=2;i--)
66

{
67

t=a[1];
68

a[1]=a[i];
69

a[i]=t;
70

len--;
72

max_heapify(1,len);
74

}
75

}
76

void heap::max_heapify(int i,int len)
79

{
80

int lt,rt;
81

int max=0;
82

lt=left(i);
84

rt=right(i);
85

if(lt<=len&&a[lt]>a[i]){
87

max=lt;
88

}
89

else{
90

max=i;
91

}
92

if(rt<=len&&a[rt]>a[max]){
94

max=rt;
95

}
96

if(max!=i){
98

int t;
99

t=a[i];
100

a[i]=a[max];
101

a[max]=t;
102

103

max_heapify(max,len);
104

}
105

}
106

107

void heap::build_heap()
108

{
109

for(int i=size/2;i>=1;i--)
110

{
111

max_heapify(i,size);
112

}
113

}
114

115

void heap::print()
116

{
117

for(int i=1;i<=size;i++)
118

{
119

cout<<a[i]<<"\t";
120

}
121

cout<<endl;
122

}
123

124

125

int main()
126

{
127

heap test(10);
128

// test.print();
129

130

131

//cout<<endl;
132

test.build_heap();
133

test.print();
134

135

cout<<endl;
136

test.heap_sort();
137

test.print() ;
138

139

}

別人的實現：
http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.4.2.2.htm
http://www.cnblogs.com/lovemo1314/archive/2011/09/13/2175032.html

posted on 2011-12-05 14:35 likun 閱讀(779) 評論(0) 編輯收藏引用所屬分類: Algorithms

只有注冊用戶登錄后才能發表評論。


相關文章: double list heap sort (Heap 的build，排序) unix的貪吃蛇小游戲已知一個函數f可以等概率的得到1-5間的隨機數，問怎么等概率的得到1-7的隨機數 red-black tree c語言實現

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品