C代码
typedef struct heap{ int capacity; // 堆的容量,即能容纳多少个有效的数据元素 int size; // 堆的当前数据量 int* data; // 指向堆中存放数据的地址,即数组的首元素 }maxHeap; maxHeap* MaxHeapInit(int capacity) { maxHeap* h = (maxHeap*)malloc(sizeof(maxHeap)); // 分配一个堆对象 if(h!=NULL) { h->capacity = capacity; // 设置堆的容量 h->size = 0; // 当前堆的数据量为零 h->data = (int*)malloc(sizeof(int)*(h->capacity+1)); // 根据堆的容量,为堆分配存放数据元素的空间 if(h->data!=NULL) { h->data[0] = INT_MAX; // 堆中的首元素是作为辅助的,不用来存放有效的数据 } else { free(h); return NULL; } } return h; } // 插入使用空穴上浮 bool MaxHeapInsert(maxHeap* obj, int x) { if(obj->size >= obj->capacity) // 插入数据元素之前,需要判断堆中是否还有空余容量 return false; else { int i = ++obj->size; // i 表示空穴的当前位置!!! while(obj->data[i/2]data[i] = obj->data[i/2]; // 将空穴的父节点值保存到空穴的位置,然后空穴就可以上浮了 i /= 2; // 空穴上浮 } obj->data[i] = x; // 当跳出循环后,说明空穴的父节点值小于空穴值,那么空穴不再上浮 return true; } } // 删除使用空穴下沉 bool MaxHeapDelete(maxHeap* obj, int* maxData) { if(obj->size==0) // 删除数据元素之前,需要判断堆中是否还存在有效数据元素 return false; else { int i = 1; // i 表示空穴的当前位置,空穴的初始位置为 1,但是空穴值却是堆中最后一个元素的值 int x = obj->data[obj->size--];//获取空穴的值 int child; // child 表示空穴的孩子的位置 *maxData = obj->data[1]; // 获得被删除的值 while(i*2<=obj->size) // 最坏的情况空穴需要下沉到叶节点, i > obj->size/2 且 i <= obj->size 的所以节点都是叶节点 { child = i*2; // 获取空穴左孩子的位置 if(child!=obj->size && obj->data[child] data[child+1]) child++; // 空穴有右孩子,且右孩子值大于左孩子,那么获取右孩子的位置 if(obj->data[child]>x) // 如果空穴的孩子的值大于空穴值,那么空穴下沉 { obj->data[i] = obj->data[child]; i = child; // 空穴下沉 } else // 如果空穴的孩子的值小于空穴值,那么空穴不再下沉,跳出循环 break; } obj->data[i] = x; return true; } }
C++代码
class maxHeap{ private: int capacity; int curSize; vectordata; public: maxHeap(int eleNums): capacity(eleNums), curSize(0) // 构造函数 { data.resize(capacity+1,0); data[0] = INT_MAX; // 索引为0的空间不存放有效数据,只作为辅助用,这个很重要 } // 插入,使用空穴上浮 void InsertElement(int x) { if(curSize >= capacity) // 插入前,先判断堆中是否还有空余容量 { capacity++; data.resize(capacity+1,x); // 扩容 } int i = curSize+1; // 空穴的初始位置 while(data[i/2] < x) // 只要空穴值大于空穴的父节点值,空穴就要上浮 { // 索引为 0 的数的作用在这体现,使循环条件更简单 data[i] = data[i/2]; // 空穴的父节点下沉 i/=2; // 空穴上浮 } data[i] = x; // 给空穴赋值 curSize++; // 堆中有效数据加一 } //删除,使用空穴下沉 void DeleteMaxElement(int& curMax) { if(curSize!=0) // 删除前先判断堆中是否还有有效数据 { curMax = data[1]; // 获取堆中当前最大值 int i = 1; // 空穴的初始位置 int x = data[curSize--]; // 空穴值取最后一个元素的值 int child; // 表示空穴孩子的位置 while(i*2<=curSize) // 空穴最多下沉到叶子节点,注意,不是一定下沉到叶子节点 { child = i*2; // 先取空穴的左孩子位置 if(child!=curSize && data[child] 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)