今天看到一道面试题，

一个最小堆，也是完全二叉树，用按层遍历数组表示。

刚看到的时候觉得挺难的，没有什么思路，原因在于对最小堆的完全二叉树不了解，其实这个二叉树和堆排序时建立的二叉树是一样的。

1、按照数组下标，下标为n的节点，它的子结点下标为2*n+1和2*n+2;

2、插入节点时，先插入到最后，然后再调整堆。

3、删除最小节点即删除根节点，先将根节点和最后一个节点交换，再调整堆。

1. #include "stdafx.h" 
2. #include<iostream>   
3. using namespace std;   
4.  
5. //往最小堆中插入元素，先插在数组的最后，然后类似于插入排序找到合适位置。 
6. void MinHeapAdd(int *a,int n,int number) 
7. {    
8.     a[n]=number; 
9.     int i=n; 
10.     int j=(i-1)/2; 
11.     int tmp=a[i]; 
12.      
13.     while(j>=0) 
14.     { 
15.         if(a[j]<=tmp) 
16.             break; 
17.         else 
18.         { 
19.             a[i]=a[j]; 
20.             i=j; 
21.             j=(i-1)/2; 
22.         } 
23.     } 
24.     a[i]=tmp; 
25. } 
26. //从第m个开始调整，n为结点总数 类似于插入排序 
27. void MinHeapFixDown(int *a,int m,int n) 
28. { 
29.     int i=m; 
30.     int j=2*i+1; 
31.     int tmp=a[i]; 
32.     while(j<n) 
33.     { 
34.         if(j+1<n&&a[j]>a[j+1]) 
35.             j++; 
36.         if(a[j]>=tmp) 
37.             break; 
38.         else 
39.         { 
40.             a[i]=a[j]; 
41.             i=j; 
42.             j=2*i+1; 
43.         } 
44.     } 
45.     a[i]=tmp; 
46. } 
47.  
48. //删除最小节点 
49. void MinHeapDelete(int *a,int n) 
50. { 
51.     a[0]=a[n-1]; 
52.     MinHeapFixDown(a,0,n-1); 
53. } 
54. //初始建堆 
55. void MakeMinHeap(int *a,int n) 
56. { 
57.     for(int i=n/2-1;i>=0;i--)//注意 
58.         MinHeapFixDown(a,i,n); 
59. } 
60. //堆排序 
61. void HeapSort(int *a,int n) 
62. { 
63.     MakeMinHeap(a,n); 
64.     for(int i=n-1;i>=1;i--) 
65.     { 
66.         int tmp=a[0];a[0]=a[i];a[i]=tmp; 
67.         MinHeapFixDown(a,0,i); 
68.     } 
69. } 
70. void main()   
71. {  
72.     int a[10]={36,30,18,40,32,45,22,50}; 
73.     HeapSort(a,8); 
74.     for(int i=0;i<8;i++) 
75.         cout<<a[i]<<" "; 
76.     cout<<endl; 
77.     int aa[10]={36,30,18,40,32,45,22,50}; 
78.     MakeMinHeap(aa,8); 
79.     for(int i=0;i<8;i++) 
80.         cout<<aa[i]<<" "; 
81.     cout<<endl; 
82.     MinHeapAdd(aa,8,35); 
83.     for(int i=0;i<9;i++) 
84.         cout<<aa[i]<<" "; 
85.     cout<<endl; 
86.     MinHeapDelete(aa,9); 
87.     for(int i=0;i<8;i++) 
88.         cout<<aa[i]<<" "; 
89.     cout<<endl; 
90.     
91. }