堆以及堆排序

  1 #include <iostream>
  2 #include <stdlib.h>
  3 using namespace std;
  4 
  5 
  6 const int MAXSIZE = 1000;
  7 
  8 //堆结构体
  9 class Heap {
 10     private:    
 11         int array[MAXSIZE];    //堆数组
 12         int size;        //实际堆节点数
 13         void init();        //初始化堆
 14         void shiftUp(int i);    //向上调整堆
 15         void shiftDown(int i, int end);//向下调整堆
 16     public:
 17         void Insert(int value);    //插入节点
 18         void Delete(int i);    //删除节点
 19         void Display();        //输出堆数组
 20         void Sort();        //堆排序
 21         Heap();
 22 };
 23 
 24 void Heap::shiftUp(int i) {
 25     int p = (i - 1) >> 1, t;    
 26     while (i > 0 && array[i] > array[p]) {//将节点key与父节点的key比较，若大于父节点，则与父节点交换位置，依次向上至根节点
 27         t = array[i];
 28         array[i] = array[p];
 29         array[p] = t;
 30         i = p;
 31         p = (i - 1) >> 1;
 32     }
 33 }
 34 
 35 void Heap::shiftDown(int i, int end) {
 36     int cl = i * 2 + 1, cr = cl + 1, t, tt = -1;
 37     while (cl <= end) {    //将结点与左右子节点较大的一个比较，若小于，则将其与该子节点交换位置，依次向下至叶子节点
 38         tt = -1;
 39         if (cr <= end) {
 40             if (array[i] < array[cl] || array[i] < array[cr]) {
 41                 tt = ((array[cl] > array[cr])?cl:cr);
 42             }
 43         } else if (array[i] < array[cl]) {
 44             tt = cl;
 45         }
 46         if (tt > 0) {
 47             t = array[i];
 48             array[i] = array[tt];
 49             array[tt] = t;
 50             i = tt;
 51             cl = i * 2 + 1;
 52                    cr = cl + 1;
 53         } else {
 54             break;
 55         }
 56     }
 57 }
 58 
 59 void Heap::Insert(int value) {
 60     if (size < MAXSIZE) {    //将节点插入至堆数组的最后，在向上进行调整堆
 61         array[size] = value;
 62         shiftUp(size++);
 63     }
 64 }
 65 
 66 void Heap::Delete(int i) {    //将堆数组最后一个节点移至要删除节点的位置，再向下调整堆
 67     if (i < size && i >= 0) {
 68         array[i] = array[size--];    
 69         shiftDown(i, size);
 70     }
 71 }
 72 
 73 void Heap::Sort() {        //将根结点与堆数组最后一个节点交换，并将堆数组节点数-1, 重新向下调整堆
 74     int i = 1, t;
 75     for (; i < size; ++i) {
 76         t = array[0];
 77         array[0] = array[size - i];
 78         array[size - i] = t;
 79         shiftDown(0, size - i - 1);
 80     }
 81 }
 82 void Heap::Display() {
 83     int j = 0;
 84     while (j < size) {
 85         cout << array[j++] << '\t';
 86     }
 87 }
 88 
 89 void Heap::init() {
 90     int randSize = rand() % 100, i = 0;
 91     size = 0;
 92     while (size < randSize) {
 93         int num = rand() % 100;
 94         Insert(num);
 95     }
 96 }
 97 
 98 Heap::Heap() {
 99     init();
100 }
101 
102 int main(int args, char **argv) {
103     Heap heap;
104     heap.Display();
105     cout << "\nafter sort:" << endl;
106     heap.Sort();
107     heap.Display();
108 }