学做招投标的网站有哪些,seo培训师,wordpress盗版插件盈利,网络营销课程总结1000字前言 普通的二叉树是不适合用数组来存储的#xff0c;因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。 现实中我们通常把堆 ( 一种二叉树 ) 使用顺序结构的数组来存储#xff0c;需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事…前言 普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。 现实中我们通常把堆 ( 一种二叉树 ) 使用顺序结构的数组来存储需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 1.堆的概念及结构 如果有一个关键码的集合 K { k0, k1,k2,…,k(n-1)},把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中并满足Ki K(2*i1)且KiK(2*i2)(Ki K(2*i1)且KiK(2*i2) i 0 1 2…则称为小堆 (或大堆) 。将根结点最大的堆叫做最大堆或大根堆根结点最小的堆叫做最小堆或小根堆。(这里的数字都是对应的下标 堆的性质 堆中某个结点的值总是不大于或不小于其父结点的值 堆总是一棵完全二叉树。 2.堆的创建和功能实现 2.1堆的基本结构的创建和相关函数声明。 #pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int Datatype;
typedef struct Heap {Datatype* a;int size;int capacity;
}HP;
// 堆的初始化
void HeapInit(HP* hp);
// 堆的销毁
void HeapDestory(HP* hp);
// 堆的插入
void HeapPush(HP* hp, Datatype x);
// 堆的删除
void HeapPop(HP* hp);
// 取堆顶的数据
Datatype HeapTop(HP* hp);
// 堆的数据个数
bool HeapSize(HP* hp);
// 堆的判空
int HeapEmpty(HP* hp);
//向上调整
void Adjustup(Datatype* a, int child);
//向下调整
void Adjustdown(Datatype* a, int n, int parent);
//数据交换
void Swap(Datatype* p1, Datatype* p2); 2.2 各函数的实现与讲解 2.1堆的初始化和销毁 堆的初始化和销毁与以前的动态数组实现顺序表和栈的初始化和销毁基本是一样的在这里小编就不多解释了。 // 堆的初始化
void HeapInit(HP* hp) {assert(hp);hp-a NULL;hp-size hp-capacity 0;
}
// 堆的销毁
void HeapDestory(HP* hp) {assert(hp);free(hp-a);hp-a NULL;hp-size hp-capacity 0;
} 2.2堆数据的插入 补充向上调整法 随便给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。根结点左右子树不是堆我们怎么调整呢 向上调整法。 通过比较新插入元素与其父节点的值来判断是否需要进行交换。如果新插入元素的值大于父节点的值就将它们进行交换并更新索引值。这样逐步向上调整直到新插入元素找到了合适的位置保证了堆的性质。 //向上调整
void Adjustup(Datatype* a,int child) {int parent (child - 1) / 2;while (child 0) {if (a[child] a[parent]) {Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
} 这个是建立大堆的向上调整建立小堆的话直接改成小于 每插入一个元素调用一次向上调整函数。 // 堆的插入
void HeapPush(HP* hp, Datatype x) {assert(hp);if (hp-size hp-capacity) {int newcapacity hp-capacity 0 ? 4 : hp-capacity * 2;Datatype* temp (Datatype*)realloc(hp-a, sizeof(Datatype) * newcapacity);if (temp NULL) {perror(realloc fail);return;}hp-a temp;hp-capacity newcapacity;}hp-a[hp-size] x;hp-size;Adjustup(hp-a, hp-size-1);
} 例如数组a[]{1, 5, 3, 8, 7, 6}依次插入并建立大堆后的顺序是 插入 1堆变为 [1]插入 5堆变为 [5, 1]插入 3堆变为 [5, 1, 3]插入 8堆变为 [8, 5, 3, 1]插入 7堆变为 [8, 7, 3, 1, 5]插入 6堆变为 [8, 7, 6, 1, 5, 3] 所以建立大堆后的顺序是 [8, 7, 6, 1, 5, 3]。 2.3堆的删除 补充向下调整法 在这里惯性思维是直接删除头顶数据然后重新建堆通过向上调整法但是我们需要从最后一个元素依次遍历向上调整。 这里我们采用向下调整法。 删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。 本张图是小堆的删除。大堆的删除方式是一样的。 因为堆数据插入是建立大堆的,所以这里的代码是大堆的向下调整。 //向下调整
void Adjustdown(Datatype* a, int n, int parent) {//假设法,假设左孩子大int child parent * 2 1;while (child n ) {if (child 1 n a[child 1] a[child])//a[child1]a[child]child child 1;if (a[child] a[parent]) { //a[child]a[parent]Swap(a[child], a[parent]);parent child;child parent * 2 1;}else break;}
} 堆的删除 // 堆的删除
void HeapPop(HP* hp) {assert(hp);assert(hp-size 0);Swap(hp-a[0], hp-a[hp-size - 1]);hp-size--;Adjustdown(hp-a, hp-size, 0);
} 最后我们会发现删除的数据是从大到小排列的,这里就可以牵扯到堆排序的应用小编在下节会讲解的。 2.4其他函数实现交换判空堆顶数据数据个数 //数据交换
void Swap(Datatype* p1, Datatype* p2) {Datatype temp *p1;*p1 *p2;*p2 temp;
}
// 取堆顶的数据
Datatype HeapTop(HP* hp) {assert(hp);assert(hp-size 0);return hp-a[0];
}
// 堆的数据个数
int HeapSize(HP* hp) {assert(hp);return hp-size;
}
// 堆的判空
bool HeapEmpty(HP* hp) {assert(hp);return hp-size 0;} 3.代码测试 #include Heap.h
void TestHeap1()
{int a[] { 4,2,8,1,5,6,9,3,2,23,55,232,66,222,33,7,66,3333,999 };//int a[] { 1,5,3,8,7,6 };HP hp;HeapInit(hp);for (int i 0; i sizeof(a) / sizeof(int); i){HeapPush(hp, a[i]);}printf(堆的大小为%d\n, HeapSize(hp));int i 0;while (!HeapEmpty(hp)){printf(%d , HeapTop(hp));//a[i] HPTop(hp);HeapPop(hp);}printf(\n);
}
/*// 找出最大的前k个int k 0;scanf(%d, k);while (k--){printf(%d , HeapTop(hp));HeapPop(hp);}printf(\n);HeapDestory(hp);
}*/
int main(){
TestHeap1();
return 0;
} 4.堆的选择题方便大家理解 1. 下列关键字序列为堆的是A A 100 , 60 , 70 , 50 , 32 , 65 B 60 , 70 , 65 , 50 , 32 , 100 C 65 , 100 , 70 , 32 , 50 , 60 D 70 , 65 , 100 , 32 , 50 , 60 E 32 , 50 , 100 , 70 , 65 , 60 F 50 , 100 , 70 , 65 , 60 , 32 2. 已知小根堆为 8 , 15 , 10 , 21 , 34 , 16 , 12 删除关键字 8 之后需重建堆在此过程中关键字之间的比较次数是C。 A 1 B 2 C 3 D 4 3. 最小堆 [ 0 , 3 , 2 , 5 , 7 , 4 , 6 , 8 ], 在删除堆顶元素 0 之后其结果是C A [ 3 2 5 7 4 6 8 ] B [ 2 3 5 7 4 6 8 ] C [ 2 3 4 5 7 8 6 ] D [ 2 3 4 5 6 7 8 ] 本节内容到此结束下次小编将讲解堆排序的知识欢迎大家捧场 期待各位友友的三连和评论
