数据结构 堆

  1 #include<iostream>
  2 #include<assert.h>
  3 #include<string>
  4 
  5  
  6 #define MAX 100
  7 using namespace std;
  8  
  9 //根据数据创建堆
 10 void CreateHeap(int *heap, int length);
 11 //向下调整堆中元素
 12 void AdjustDownHeap(int *heap, int i, int length);
 13 //向上调整堆中元素
 14 void AdjustUpHeap(int *heap, int i, int length);
 15 //向堆中插入元素
 16 int InsertHeap(int *heap, int length, int x);
 17 //删除元素，每次只能删除根节点
 18 int DeleteHeap(int *heap, int length);
 19 //堆排序
 20 void SortHeap(int *heap, int length);
 21 int main()
 22 {
 23     int heap[7] = {4,5,6,9,8,7};
 24     printf("根据所给数组元素创建大根堆：");
 25     CreateHeap(heap,6);
 26     for (int i = 0; i < 6;i++)
 27     {
 28         printf("%d ",heap[i]);
 29     }
 30     printf("\n");
 31     printf("插入元素10，向上调整：");
 32     InsertHeap(heap,6,10);
 33     for (int i = 0; i < 7; i++)
 34     {
 35         printf("%d ", heap[i]);
 36     }
 37     printf("\n");
 38     printf("删除根节点，调整为大根堆：");
 39     DeleteHeap(heap, 7);
 40     for (int i = 0; i < 6; i++)
 41     {
 42         printf("%d ", heap[i]);
 43     }
 44     printf("\n");
 45     printf("根据大根堆进行堆排序：");
 46     SortHeap(heap, 6);
 47     for (int i = 0; i < 6; i++)
 48     {
 49         printf("%d ", heap[i]);
 50     }
 51     printf("\n");
 52     return 0;
 53 }
 54  
 55 void CreateHeap(int *heap,int length)
 56 {
 57     for (int i = length / 2-1; i >= 0;i--)
 58     {
 59         AdjustDownHeap(heap, i, length);
 60     }
 61 }
 62  
 63 
 64 void AdjustDownHeap(int *heap,int i,int length)
 65 {
 66     int temp = 0;
 67     int nChild;
 68     while ((2 * i + 1)<length)
 69     {
 70         nChild = 2 * i + 1;
 71         if (heap[nChild]<heap[nChild + 1] && nChild+1<length)
 72         {
 73             nChild++;
 74         }
 75         if (heap[i]<heap[nChild])
 76         {
 77             temp = heap[i];
 78             heap[i] = heap[nChild];
 79             heap[nChild] = temp;
 80             i = nChild;
 81         }
 82         else
 83         {
 84             break;
 85         }
 86     }
 87 }
 88  
 89 int InsertHeap(int *heap,int length,int x)
 90 {
 91     int i = length;
 92     int temp = 0;
 93     heap[length] = x;
 94     while (i>0)
 95     {
 96         if (heap[i]>heap[(i-1)/2])
 97         {
 98             temp = heap[i];
 99             heap[i] = heap[(i - 1) / 2];
100             heap[(i - 1) / 2] = temp;
101             i = (i-1) / 2;
102         }
103         else
104         {
105             break;
106         }
107     }
108     //返回插入位置
109     return i;
110 }
111 int DeleteHeap(int *heap, int length)
112 {
113     int topNum = heap[0];
114     heap[0] = heap[length-1];
115     AdjustDownHeap(heap,0,length-1);
116     //返回根节点元素
117     return topNum;
118 }
119 //堆排序
120 void SortHeap(int *heap, int length)
121 {
122     int index = length - 1;
123     int temp = 0;
124     int num = 0;
125     while (index > 0)
126     {
127         temp = heap[0];
128         heap[0] = heap[index];
129         heap[index] = temp;
130         AdjustDownHeap(heap, 0, index);
131         index--;
132     }
133  
134 }