共两部分 C 实现 & C++类的编写
-------------------------------------C实现------------------------------------------
1 通过堆的性质 编写优先队列
2 堆中的元素可根据实际需要 存储相应的值（可以是指针，结构体 或者 是一个对象），
此处简单起见使用了整数
1 //保持最大堆性质 参数inode为内部结点 注意结点从1开始，数组从0开始 2 void MaxHeapify(int array[], int size, int inode) 3 { 4 int largest= inode; //父结点 5 int left = inode*2; //左子结点 6 int right = inode*2+1; //右子结点 7 8 if (left <= size && array[left-1] > array[largest-1]) 9 { 10 largest = left; 11 } 12 if (right <= size && array[right-1] > array[largest-1]) 13 { 14 largest = right; 15 } 16 17 if (largest != inode) //父结点小于 左子结点 或者 右子结点 18 { 19 int temp = array[inode-1]; //子结点值与父结点值交换 20 array[inode-1] = array[largest-1]; 21 array[largest-1] = temp; 22 23 MaxHeapify(array, size, largest); //再次验证被交换的值的子结点是否满足 最大堆性质 24 } 25 } 26 //建立最大堆 使每一个父结点大于子结点 27 void BuildMaxHeap(int array[],int size) 28 { 29 for(int i=size/2; i>0; --i) //最多有 size/2 个内部结点 30 { 31 MaxHeapify(array, size, i); 32 } 33 } 34 //堆排序 35 void HeapSort(int array[], int size) 36 { 37 BuildMaxHeap(array, size); //建立最大堆 结果是最大值 为根结点 38 int temp = 0; 39 int heapSize = size; 40 for (int i=size; i>1; --i) 41 { 42 temp=array[0]; //交换 根结点的值 与 最后面末尾的结点的值 43 array[0]=array[i-1]; //此时违背了最大堆的性质 44 array[i-1] = temp; 45 46 --heapSize; //保持最大堆的性质之前 先去掉已排好序的元素，即减小堆的大小 47 MaxHeapify(array, heapSize, 1); 48 } 49 }; 50 //返回堆中最大的值 51 int HeapMax(int array[], int size) 52 { 53 return array[0]; 54 } 55 //去掉并返回堆中最大的值，同时去掉最大值之后仍然保持最大堆的性质 56 int HeapExtractMax(int array[], int size) 57 { 58 if (size < 0) 59 { 60 return -1; 61 } 62 else if(size == 1) 63 { 64 return array[0]; 65 } 66 67 int max = array[0]; 68 array[0] = array[size-1]; 69 --size; 70 MaxHeapify(array, size, 1); 71 72 return max; 73 } 74 75 //增加指定关键字的值（此处是通过下标指定关键字,从1开始） 76 void HeapIncreaseKey(int array[], int size, int index, int key) 77 { 78 if(key<array[index-1]) //指定增加的值必须大于原先的值 79 return; 80 array[index-1] = key; 81 82 while(index>1 && array[index/2-1] < array[index-1]) 83 { 84 int tmp = array[index-1]; 85 array[index-1] = array[index/2-1]; 86 array[index/2-1] = tmp; 87 index = index/2; 88 } 89 } 90 //删除指定关键字的值，保持最大堆得性质 91 void HeapDelete(int array[], int size, int index) 92 { 93 array[index-1] = array[size-1]; 94 --size; 95 MaxHeapify(array, size, index); //确保index下的结点满足最大堆性质 96 97 while(index>1 && array[index/2-1] < array[index-1]) //确保index的父结点满足最大堆性质 98 { 99 int tmp = array[index-1]; 100 array[index-1] = array[index/2-1]; 101 array[index/2-1] = tmp; 102 index = index/2; 103 } 104 105 } 106 //实现最大堆的插入操作，即给堆中插入新值，并且保持最大堆的性质 107 void HeapInsert(int array[], int size, int key) 108 { 109 size = size+1; //确保数组足够大不溢出 110 array[size-1] = 0; //此处直接复用HeapIncreaseKey，确保函数的性质 111 HeapIncreaseKey(array, size, size, key); 112 } 113 114 void main() 115 { 116 //_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); 117 118 int Array[12] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; 119 120 BuildMaxHeap(Array, 10); 121 122 for (int i=0; i<10; ++i) 123 { 124 cout << Array[i] << " "; 125 } 126 cout << " HeapMax：" << HeapMax(Array, 10) << endl; 127 128 cout <<" HeapExtractMax: " << HeapExtractMax(Array, 10) << endl<<endl; 129 130 HeapIncreaseKey(Array, 9, 2, 20); 131 for (int i=0; i<9; ++i) 132 { 133 cout << Array[i] << " "; 134 } 135 HeapInsert(Array, 9, 17); 136 cout << endl; 137 for (int i=0; i<10; ++i) 138 { 139 cout << Array[i] << " "; 140 } 141 HeapDelete(Array, 10, 1); 142 cout << endl; 143 for (int i=0; i<10; ++i) 144 { 145 cout << Array[i] << " "; 146 } 147 148 system("pause"); 149 }
------------------------------------C++类的编写-----------------------------------
1 通过C实现可改写成 优先队列的类
2 改写类的时候，确保抽象接口的一致性
1 const int SIZE = 100; 2 class Queue 3 { 4 private: 5 int queue[SIZE]; 6 int count; //当前队列里的个数 7 void MaxHeapify(int inode); //向下确保堆的最大性质 8 void MaxHeapify_check_parent(int inode); // 向上确保堆得最大性质 9 void BuildMaxHeap(); 10 public: 11 void HeapSort(); 12 int HeapMax(); 13 int HeapExtractMax(); 14 void HeapIncreaseKey(int index, int key); 15 void HeapDelete(int index); 16 void MaxHeapInsert(int key); 17 bool Empty(); 18 };