[数据结构]堆排序

1,堆排序
概念

点击打开链接

点击打开链接

堆排序与快速排序，归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2

堆的插入与删除
堆的插入：每次插入都是将新数据放在数组最后
堆的删除：
按定义，堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。
堆排序：
首先可以看到堆建好之后堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。
这样堆中第0个数据又是堆中最小的数据，重复上述步骤直至堆中只有一个数据时就直接取出这个数据。

[cpp] view plaincopy

 

1. 建堆过程C语言表示：  
2.    1: /* 
3.    2:     输入：数组A，堆的长度hLen，以及需要调整的节点i 
4.    3:     功能：调堆 
5.    4: */  
6.    5:    
7.    6: void AdjustHeap(int A[], int hLen, int i)  
8.    7: {  
9.    8:     int left = LeftChild(i);  //节点i的左孩子  
10.    9:     int right = RightChild(i); //节点i的右孩子节点  
11.   10:     int largest = i;  
12.   11:     int temp;  
13.   12:    
14.   13:     while(left < hLen || right < hLen)  
15.   14:     {  
16.   15:         if (left < hLen && A[largest] < A[left])  
17.   16:         {  
18.   17:             largest = left;  
19.   18:         }  
20.   19:           
21.   20:         if (right < hLen && A[largest] < A[right])  
22.   21:         {  
23.   22:             largest = right;  
24.   23:         }  
25.   24:    
26.   25:         if (i != largest)   //如果最大值不是父节点  
27.   26:         {  
28.   27:              temp = A[largest]; //交换父节点和和拥有最大值的子节点交换  
29.   28:              A[largest] = A[i];  
30.   29:              A[i] = temp;  
31.   30:    
32.   31:             i = largest;         //新的父节点，以备迭代调堆  
33.   32:             left = LeftChild(i);  //新的子节点  
34.   33:             right = RightChild(i);  
35.   34:         }  
36.   35:         else  
37.   36:         {  
38.   37:             break;  
39.   38:         }  
40.   39:     }  
41.   40: }  
42.   41:    
43.   42: /* 
44.   43:     输入：数组A，堆的大小hLen 
45.   44:     功能：建堆 
46.   45: */  
47.   46: void BuildHeap(int A[], int hLen)  
48.   47: {  
49.   48:     int i;  
50.   49:     int begin = hLen/2 - 1;  //最后一个非叶子节点  
51.   50:     for (i = begin; i >= 0; i--)  
52.   51:     {  
53.   52:         AdjustHeap(A, hLen, i);    
54.   53:     }  
55.   54: }  
56.   55:    
57.   56: /* 
58.   57:     输入：数组A，待排序数组的大小aLen 
59.   58:     功能：堆排序 
60.   59: */  
61.   60: void HeapSort(int A[], int aLen)  
62.   61: {  
63.   62:     int hLen = aLen;  
64.   63:     int temp;  
65.   64:    
66.   65:     BuildHeap(A, hLen);      //建堆  
67.   66:    
68.   67:     while (hLen > 1)  
69.   68:     {  
70.   69:         temp = A[hLen-1];    //交换堆的第一个元素和堆的最后一个元素  
71.   70:         A[hLen-1] = A[0];  
72.   71:         A[0] = temp;  
73.   72:         hLen--;        //堆的大小减一  
74.   73:         AdjustHeap(A, hLen, 0);  //调堆  
75.   74:     }  
76.   75: }  

[数据结构]堆排序

原文：http://www.cnblogs.com/zhiliao112/p/4237168.html