为什么苏州网络进不了网站,安阳贴吧论坛,台州企业网站,动图在线制作网站【0】README
1#xff09;本文旨在给出 二叉堆优先队列的实现 的代码实现和分析#xff0c; 而堆节点类型 不外乎三种#xff1a; 一#xff0c; 基本类型如int#xff1b; 二#xff0c;结构体类型 struct HeapNode#xff1b; 三#xff0c;结构体指针类型 struct H…【0】README
1本文旨在给出 二叉堆优先队列的实现 的代码实现和分析 而堆节点类型 不外乎三种 一 基本类型如int 二结构体类型 struct HeapNode 三结构体指针类型 struct HeapNode* 类型
2为什么要给出 结构体指针类型的 二叉堆实现 因为 小生我在 实现 克鲁斯卡尔算法 求 最小生成树的时候需要用到 二叉堆优先队列 选取 权值最小的边所以要用到 结构体指针类型的 二叉堆实现 哥子 今天一上午 也 没有 吧 kruskal alg 实现出来原因就在于 结构体指针类型 的 二叉堆 没有 弄清楚
3本文末尾对三种堆节点类型的源码实现 进行了分析和比较
4for full source code, please visit https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter6/review
5wc 刚才填了一个大坑你懂的。 // for循环的 leftChild(index) size 必须要取 等号.for(temp data[index]; leftChild(index) size; index child){child leftChild(index);if(child size data[child] data[child1]) // if 语句里的 child size 不取等号.【1】二叉堆基本操作 操作1初始化堆 操作2基于上滤操作的插入操作 操作3基于下滤操作的删除最小值 deleteMin 操作4decreaseKey 操作 操作5increaseKey 操作 【2】基本类型int为堆节点的堆实现
1堆结构体 // 堆节点类型为 int.
#define ElementType intstruct BinaryHeap;
typedef struct BinaryHeap *BinaryHeap;
struct BinaryHeap
{int capacity;int size; ElementType *array;
};
2源码实现 // judge whether the BinaryHeap is full or not , also 1 or 0 .
// you should know the element under index 0 dont store any content.
int isFull(BinaryHeap bh)
{return bh-size bh-capacity - 1 ? 1 : 0 ;
}// judge whether the BinaryHeap is empty or not , also 1 or 0
int isEmpty(BinaryHeap bh)
{return bh-size 0 ? 1 : 0 ;
}void swap(ElementType *x, ElementType *y)
{ElementType temp;temp *x;*x *y;*y temp;
}// get the left child of node under index with startup 1
int leftChild(int index)
{return index*2;
}// initialize binary heap with given capacity.
BinaryHeap initBinaryHeap(int capacity)
{BinaryHeap bh;ElementType *temp;bh (BinaryHeap)malloc(sizeof(struct BinaryHeap));if(!bh) {Error(out of space, from func initBinaryHeap); return NULL;} bh-capacity capacity;bh-size 0;temp (ElementType *)malloc(capacity * sizeof(ElementType));if(!temp) {Error(out of space, from func initBinaryHeap); return NULL;} bh-array temp;bh-array[0] INT_MIN; // let bh-array[0] be the minimum integer.return bh;
}// Attention, the index of the heap starts from 1
// insert the value into binary heap based on percolateUp().
void insert(ElementType value, BinaryHeap bh)
{ if(isFull(bh)){Error(failed insertion , for the BinaryHeap is full, from func insert!);return ; }bh-array[bh-size] value; // startup is 1 not 0.percolateUp(bh-size, bh);
}// percolating up the element when its value is greater than children (minimal heap)//Attention: all of bh-array starts from index 1
void percolateUp(int i, BinaryHeap bh)
{ ElementType temp bh-array[i];for(; temp bh-array[i/2]; i/2){bh-array[i] bh-array[i/2];}bh-array[i] temp;
}// delete minimal from binary heap based on percolateDown().
ElementType deleteMin(BinaryHeap bh)
{ ElementType minimum;ElementType *data; if(isEmpty(bh)){Error(failed deleting minimum , for the BinaryHeap is empty, from func deleteMin !);return -1; }data bh-array; minimum data[1];swap(data[1], data[bh-size]); // variable means nickname of the variablebh-size-- ; // size-- occurs prior to percolateDown(). percolateDown(1, bh) ; return minimum;
} // percolating down the element when its value is greater than children (minimal heap)//Attention: all of bh-array starts from index 1void percolateDown(int index, BinaryHeap bh){ ElementType *data;int size;ElementType temp;int child;data bh-array;size bh-size;for(temp data[index]; leftChild(index) size; index child){child leftChild(index);if(child size data[child] data[child1]){child;}if(temp data[child]){data[index] data[child];}else{break;}}data[index] temp;}// print binary heap.
void printBinaryHeap(BinaryHeap bh)
{int i;ElementType *temp;if(!bh){Error(printing execution failure, for binary heap is null, from func printBinaryHeap); }temp bh-array;for(i1; i bh-size; i){printf(\n\t index[%d] , i); printf(%d, bh-array[i]); }printf(\n);
} // increase elements value
void increaseKey(int index, ElementType increment, BinaryHeap bh)
{ if(index bh-size || index 1){Error( failed increaseKey, since overstep the boundary! );return ;}bh-array[index] increment; // update the element under given indexpercolateDown(index, bh);
}//decreasing value of the element under index by increment
void decreaseKey(int index, ElementType decrement, BinaryHeap bh)
{ if(index bh-size || index 1){Error( failed decreaseKey, since overstep the boundary! );return ;}bh-array[index] - decrement; // update the element under given indexpercolateUp(index, bh);
}
3测试用例 int main()
{int i;BinaryHeap bh;int capacity;int size;ElementType data[] {85, 80, 40, 30, 10, 70, 110};capacity 15;size 7;bh initBinaryHeap(capacity);printf(\ninsert {85, 80, 40, 30, 10, 70, 110} into binary heap.);for(i 0; i size; i){insert(data[i], bh);} printBinaryHeap(bh);printf(\ninsert {100, 20, 90, 5} into binary heap\n);insert(100, bh);insert(20, bh);insert(90, bh);insert(5, bh);printBinaryHeap(bh);printf(\ndeleteMin from binary heap\n);deleteMin(bh); printBinaryHeap(bh); // other operations in bianry heap printf(\nincreaseKey(2, 85, bh) [increaseKey(index, increment, binary heap)]\n);increaseKey(2, 85, bh);printBinaryHeap(bh);printf(\ndecreaseKey(9, 85, bh) [decreaseKey(index, decrement, binary heap)]\n);decreaseKey(9, 85, bh);printBinaryHeap(bh);return 0;
} 【3】结构体类型struct HeapNode为堆节点的堆实现 1堆结构体 // 堆节点类型是结构体.
struct HeapNode;
typedef struct HeapNode* HeapNode;
struct HeapNode
{int value;
};// 二叉堆的结构体.
struct BinaryHeap;
typedef struct BinaryHeap *BinaryHeap;
struct BinaryHeap
{int capacity;int size; HeapNode array; // 二叉堆实现为结构体数组.
};
// 堆节点类型是 结构体类型 而不是单纯的 int类型.
#define ElementType struct HeapNode
2源码实现 ElementType createElementType(int value)
{struct HeapNode node;node.value value;return node;
}// judge whether the BinaryHeap is full or not , also 1 or 0 .
// you should know the element under index 0 dont store any content.
int isFull(BinaryHeap bh)
{return bh-size bh-capacity - 1 ? 1 : 0 ;
}// judge whether the BinaryHeap is empty or not , also 1 or 0
int isEmpty(BinaryHeap bh)
{return bh-size 0 ? 1 : 0 ;
}void swap(ElementType *x, ElementType *y)
{ElementType temp;temp *x;*x *y;*y temp;
}// get the left child of node under index with startup 1
int leftChild(int index)
{return index*2;
}// initialize binary heap with given capacity.
BinaryHeap initBinaryHeap(int capacity)
{BinaryHeap bh;ElementType *temp;bh (BinaryHeap)malloc(sizeof(struct BinaryHeap));if(!bh) {Error(out of space, from func initBinaryHeap); return NULL;} bh-capacity capacity;bh-size 0;temp (ElementType *)malloc(capacity * sizeof(ElementType));if(!temp) {Error(out of space, from func initBinaryHeap); return NULL;} bh-array temp;bh-array[0].value INT_MIN; // update: let bh-array[0]-value be the minimum integer.return bh;
}// Attention, the index of the heap starts from 1
// insert the value into binary heap based on percolateUp().
void insert(ElementType e, BinaryHeap bh)
{ if(isFull(bh)){Error(failed insertion , for the BinaryHeap is full.);return ; }bh-array[bh-size] e; // startup is 1 not 0.percolateUp(bh-size, bh);
}// percolating up the element when its value is greater than children (minimal heap)//Attention: all of bh-array starts from index 1
void percolateUp(int i, BinaryHeap bh)
{ ElementType temp bh-array[i];for(; temp.value bh-array[i/2].value; i/2) // update.{bh-array[i] bh-array[i/2];}bh-array[i] temp;
}// delete minimal from binary heap based on percolateDown().
ElementType deleteMin(BinaryHeap bh)
{ ElementType minimum;ElementType *data; data bh-array; minimum data[1];swap(data[1], data[bh-size]); // variable means nickname of the variablebh-size-- ; // size-- occurs prior to percolateDown(). percolateDown(1, bh) ; return minimum;
} // percolating down the element when its value is greater than children (minimal heap)//Attention: all of bh-array starts from index 1void percolateDown(int index, BinaryHeap bh){ ElementType* array; int size;ElementType temp;int child;array bh-array;size bh-size;for(temp array[index]; leftChild(index) size; index child){child leftChild(index);if(child size array[child].value array[child1].value){child;}if(temp.value array[child].value){array[index] array[child];}else{break;}}array[index] temp;}// print binary heap.
void printBinaryHeap(BinaryHeap bh)
{int i;ElementType *temp;if(!bh){Error(printing execution failure, for binary heap is NULL.); }temp bh-array;for(i 1; i bh-size; i){printf(\n\t index[%d] , i); printf(%d, bh-array[i]);}printf(\n);
} // increase elements value
void increaseKey(int index, int increment, BinaryHeap bh)
{ if(index bh-size || index 1){Error( failed increaseKey, since overstep the boundary! );return ;}bh-array[index].value increment; // update the element under given indexpercolateDown(index, bh);
}//decreasing value of the element under index by increment
void decreaseKey(int index, int decrement, BinaryHeap bh)
{ if(index bh-size || index 1){Error( failed decreaseKey, since overstep the boundary! );return ;}bh-array[index].value - decrement; // update the element under given indexpercolateUp(index, bh);
} 3测试用例 // 堆节点是结构体类型.
int main()
{ BinaryHeap bh;int i, capacity, size; int data[] {85, 80, 40, 30, 10, 70, 110};capacity 15;size 7;bh initBinaryHeap(capacity);printf(\ninsert {85, 80, 40, 30, 10, 70, 110} into binary heap with heap node being struct.);for(i 0; i size; i){insert(createElementType(data[i]), bh);} printBinaryHeap(bh);printf(\ninsert {100, 20, 90, 5} into binary heap\n);insert(createElementType(100), bh);insert(createElementType(20), bh);insert(createElementType(90), bh);insert(createElementType(5), bh);printBinaryHeap(bh);printf(\ndeleteMin from binary heap\n);deleteMin(bh); printBinaryHeap(bh); // other operations in bianry heap printf(\nincreaseKey(2, 85, bh) [increaseKey(index, increment, binary heap)]\n);increaseKey(2, 85, bh);printBinaryHeap(bh);printf(\ndecreaseKey(9, 85, bh) [decreaseKey(index, decrement, binary heap)]\n);decreaseKey(9, 85, bh);printBinaryHeap(bh);return 0;
} 【4】结构体类型指针struct HeapNode*为堆节点的堆实现
1堆结构体 struct HeapNode;
typedef struct HeapNode* HeapNode;
struct HeapNode
{int value;
};// 二叉堆的结构体.
struct BinaryHeap;
typedef struct BinaryHeap *BinaryHeap;
struct BinaryHeap
{int capacity;int size; HeapNode* array; // 堆节点类型是结构体指针. 而优先队列是结构体指针数组.
};
// 堆节点类型是 结构体指针类型 而不是单纯的 int类型.
#define ElementType HeapNode 2源码实现 ElementType createElementType(int value)
{HeapNode node (HeapNode)malloc(sizeof(struct HeapNode));if(node NULL){Error(failed createElementType() for out of space.); return NULL;}node-value value;return node;
}// judge whether the BinaryHeap is full or not , also 1 or 0 .
// you should know the element under index 0 dont store any content.
int isFull(BinaryHeap bh)
{return bh-size bh-capacity - 1 ? 1 : 0 ;
}// judge whether the BinaryHeap is empty or not , also 1 or 0
int isEmpty(BinaryHeap bh)
{return bh-size 0 ? 1 : 0 ;
}void swap(ElementType x, ElementType y)
{struct HeapNode temp;temp *x;*x *y;*y temp;
}// get the left child of node under index with startup 1
int leftChild(int index)
{return index*2;
}// initialize binary heap with given capacity.
BinaryHeap initBinaryHeap(int capacity)
{BinaryHeap bh;ElementType* temp;bh (BinaryHeap)malloc(sizeof(struct BinaryHeap));if(!bh) {Error(out of space, from func initBinaryHeap); return NULL;} bh-capacity capacity;bh-size 0;temp (ElementType *)malloc(capacity * sizeof(ElementType));if(!temp) {Error(out of space, from func initBinaryHeap); return NULL;} bh-array temp;// bh-array[0] INT_MIN; bh-array[0] (ElementType)malloc(sizeof(struct HeapNode));if(bh-array[0] NULL){Error(out of space, from func initBinaryHeap); return NULL;}bh-array[0]-value INT_MIN; return bh;
}// Attention, the index of the heap starts from 1
// insert the value into binary heap based on percolateUp().
void insert(ElementType e, BinaryHeap bh)
{ if(e NULL){Error(failed insertion , for e is NULL.);return;}if(isFull(bh)){Error(failed insertion , for the BinaryHeap is full.);return ; }bh-array[bh-size] e; // startup is 1 not 0.percolateUp(bh-size, bh);
}// percolating up the element when its value is greater than children (minimal heap)//Attention: all of bh-array starts from index 1
void percolateUp(int i, BinaryHeap bh)
{ ElementType temp bh-array[i];for(; temp-value bh-array[i/2]-value; i/2) // update.{bh-array[i] bh-array[i/2];}bh-array[i] temp;
}// delete minimal from binary heap based on percolateDown().
ElementType deleteMin(BinaryHeap bh)
{ ElementType minimum;ElementType* array; array bh-array; minimum array[1];swap(array[1], array[bh-size]); // variable means nickname of the variablebh-size-- ; // size-- 在下滤函数执行之前发生.percolateDown(1, bh) ; return minimum;
} // percolating down the element when its value is greater than children (minimal heap)//Attention: all of bh-array starts from index 1void percolateDown(int index, BinaryHeap bh){ ElementType* array; int size;ElementType temp;int child;array bh-array;size bh-size;for(temp array[index]; leftChild(index) size; index child){child leftChild(index);if(child size array[child]-value array[child1]-value){child;}if(temp-value array[child]-value){array[index] array[child];}else{break;}}array[index] temp;}// print binary heap.
void printBinaryHeap(BinaryHeap bh)
{int i;if(!bh){Error(printing execution failure, for binary heap is NULL.); return;}for(i1; i bh-size; i){printf(\n\t index[%d] , i); printf(%d, bh-array[i]-value); }printf(\n);
} // increase elements value
void increaseKey(int index, int increment, BinaryHeap bh)
{ if(index bh-size || index 1){Error( failed increaseKey, since overstep the boundary! );return ;}bh-array[index]-value increment; // update the element under given indexpercolateDown(index, bh);
}//decreasing value of the element under index by increment
void decreaseKey(int index, int decrement, BinaryHeap bh)
{ if(index bh-size || index 1){Error( failed decreaseKey, since overstep the boundary! );return ;}bh-array[index]-value - decrement; // update the element under given indexpercolateUp(index, bh);
}3测试用例// 堆节点是结构体指针类型.
int main()
{ BinaryHeap bh;int i, capacity, size; int data[] {85, 80, 40, 30, 10, 70, 110};capacity 15;size 7;bh initBinaryHeap(capacity);printf(\ninsert {85, 80, 40, 30, 10, 70, 110} into binary heap.);for(i 0; i size; i){insert(createElementType(data[i]), bh);} printBinaryHeap(bh);printf(\ninsert {100, 20, 90, 5} into binary heap\n);insert(createElementType(100), bh);insert(createElementType(20), bh);insert(createElementType(90), bh);insert(createElementType(5), bh);printBinaryHeap(bh);printf(\ndeleteMin from binary heap\n);deleteMin(bh); printBinaryHeap(bh); // other operations in bianry heap printf(\nincreaseKey(2, 85, bh) [increaseKey(index, increment, binary heap)]\n);increaseKey(2, 85, bh);printBinaryHeap(bh);printf(\ndecreaseKey(9, 85, bh) [decreaseKey(index, decrement, binary heap)]\n);decreaseKey(9, 85, bh);printBinaryHeap(bh);return 0;
} 【5】堆节点为 或者int类型 或者结构体类型 或者 结构体指针类型 的源码分析和总结
1注意在以上实现中 哪些函数是相同的哪些函数是不同的 就算有些函数声明相同但是函数体是不同的
2要知道 堆的第一个存储空间不用index 0对于int 类型的处理方式是 设置 array[0]INT_MIN 对于 struct 类型的处理方式是 array[0].value INT_MIN对于 struct* 类型的处理方式是 array[0]-value INT_MIN这都是为了 上滤的时候 便于比较而对于 array[0] 的初始化都是在 初始化堆中的函数完成的
3还有一个需要注意的是 swap() 函数deleteMin() 函数 需要用到 swap函数因为 在 删除最小元元素的时候是吧 第一个元素 和 最后一个元素进行交换然后size--然后再对 index1 的元素进行下滤操作所以 swap() 交换函数特别重要 void swap(ElementType x, ElementType y) // struct HeapNode* 的 swap函数.堆节点类型是 结构体指针类型
{struct HeapNode temp;temp *x;*x *y;*y temp;
}
void swap(ElementType *x, ElementType *y) // struct HeapNode 的swap函数.堆节点类型是 结构体类型
{ElementType temp;temp *x;*x *y;*y temp;
}
void swap(ElementType *x, ElementType *y) // int 类型的swap函数堆节点类型是 int基本类型
{ElementType temp;temp *x;*x *y;*y temp;
}
4测试用例中插入元素进堆传入的参数不一样虽然 他们的 insert 函数都是 void insert(ElementType value, BinaryHeap bh)对于 int类型来说 ElementType 就是 int 对于 struct HeapNode 来说ElementType 就是 struct HeapNode 而对于 struct HeapNode* 来说 ElementType 就是 struct HeapNode*所以你看到在不同测试用例中除开 int 基本类型 都是要 创建 堆节点的然后再传入 ElementType createElementType(int value) // struct HeapNode 类型的 createElementType() 函数体
{struct HeapNode node;node.value value;return node;
}
ElementType createElementType(int value) // struct HeapNode* 类型的 createElemnetType() 函数体. 是很不一样的这是我们需要注意的.
{HeapNode node (HeapNode)malloc(sizeof(struct HeapNode));if(node NULL){Error(failed createElementType() for out of space.); return NULL;}node-value value;return node;
}
