怎么做单页网站导航,黑群辉建设个人网站,建筑网站模板,seo网站优化方案书#x1f95d;堆 堆总是一棵完全二叉树。 大堆#xff1a;父节点总是大于子节点。 小堆#xff1a;父节点总是小于子节点。 注意#xff1a;1.同一个节点下的两个子节点并无要求先后顺序。 2.堆可以是无序的。
#x1f349;堆的实现
#x1f334;深度剖析
1.父节点和子…
堆 堆总是一棵完全二叉树。 大堆父节点总是大于子节点。 小堆父节点总是小于子节点。 注意1.同一个节点下的两个子节点并无要求先后顺序。 2.堆可以是无序的。
堆的实现
深度剖析
1.父节点和子节点之间的关系
子节点父节点*21
或者子节点父节点*22
父节点子节点-1/2
2.堆的插入HeapPush实现 先插入一个10到数组的尾上再进行向上调整算法直到满足堆 void HeapPush(Heap* php, HPDataType x) {assert(php);if (php-size php-capacity) {int newcapacity 0 ? 4 : 2 * php-capacity;HPDataType* tmp (HPDataType*)malloc(sizeof(HPDataType) * newcapacity);if (tmp NULL) {perror(malloc fail!);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;AdjustUp(php-a,php-size);php-size;
} 3.堆的删除HeapPop函数的实现
函数目的删除堆顶元素
为了避免破坏堆的整体结构先将首尾元素进行交换再对首元素进行向下调整直到满足堆。最后php-size--即可删除原栈顶元素。
void HeapPop(Heap* php) {assert(php);swap(php-a[0], php-a[php-size - 1]);AdjustDown(php-a, php-size,0);php-size--;
}代码实现
Heap.h
#include stdio.h
#include assert.h
#include stdlib.h
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
int HeapSize(Heap* php);
// 堆的判空
int HeapEmpty(Heap* php);Heap.c
#define _CRT_SECURE_NO_WARNINGS
#include Heap.h
void HeapInit(Heap* php) {assert(php);php-a NULL;php-capacity php-size 0;
}void HeapDestory(Heap* php) {assert(php);free(php-a);php-a NULL;php-capacity php-size 0;
}void swap(int* a, int* b) {int tmp *a;*a *b;*b tmp;
}
//小堆
void AdjustUp(HPDataType* a,int child) {assert(a);int parent (child - 1) / 2;while (child 0) {if (a[parent] a[child]) {swap(a[parent], a[child]);child parent;parent (child - 1) / 2;}else {break;}}
}void HeapPush(Heap* php, HPDataType x) {assert(php);if (php-size php-capacity) {int newcapacity 0 ? 4 : 2 * php-capacity;HPDataType* tmp (HPDataType*)malloc(sizeof(HPDataType) * newcapacity);if (tmp NULL) {perror(malloc fail!);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;AdjustUp(php-a,php-size);php-size;
}
//从给定的子节点开始不断向上与其父节点进行比较和可能的交换直到达到根节点或找到一个满足最大堆性质的父节点为止。
void AdjustDown(int* a, int n, int parent) {assert(a);int child parent * 2 1;while (child n) {if (child 1 n a[child] a[child 1]) {child;}if (a[parent] a[child]) {swap(a[parent], a[child]);parent child;child parent * 2 1;}else {break;}}
}void HeapPop(Heap* php) {assert(php);swap(php-a[0], php-a[php-size - 1]);AdjustDown(php-a, php-size,0);php-size--;
}HPDataType HeapTop(Heap* php) {assert(php);assert(php-size 0);return php-a[0];
}int HeapSize(Heap* php) {assert(php);return php-size;
}int HeapEmpty(Heap* php) {assert(php);return php-size;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include Heap.h
int main() {Heap hp;HeapInit(hp);HeapPush(hp, 7);HeapPush(hp, 6);HeapPush(hp, 5);HeapPush(hp, 4);HeapPush(hp, 3);HeapPush(hp, 2);HeapPush(hp, 1);for (int i 0; i hp.size; i) {printf(%d , hp.a[i]);}HeapPop(hp);printf(\n);for (int i 0; i hp.size; i) {printf(%d , hp.a[i]);}printf(\n);printf(堆顶元素为%d\n, HeapTop(hp));if (HeapEmpty(hp)) {printf(堆不为空\n);}else {printf(堆为空\n);}return 0;
}
堆排序
深度剖析
第一步建堆
升序建大堆降序建小堆
以升序为例
从最后一个父节点开始向前遍历向上调整(大的上小的下。 //建堆从倒数第一个父节点开始向前遍历向下调整for (int i (n-1-1)/2; i 0 ;i--) {AdjustDown(a,n,i);}
第二步排序
1.首尾元素交换左图
2.再向下调整大的上小的下这样调整后的堆顶元素必为调整范围内的最大值经过下一轮的首尾元素交换后就可以放入调整完的区域内。 while (n - 1) {swap(a[0], a[n - 1]);AdjustDown(a, n-1,0);n--;
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include assert.hvoid swap(int* a, int* b) {int tmp *a;*a *b;*b tmp;
}void AdjustUp(int* a, int child) {assert(a);int parent (child - 1) / 2;while (child 0) {if (a[parent] a[child]) {swap(a[parent], a[child]);child parent;parent (child - 1) / 2;}else {break;}}
}
void AdjustDown(int* a, int n, int parent) {assert(a);int child parent * 2 1;while (child n ) {if (child 1 n a[child] a[child 1]) {child;}if (a[parent] a[child]) {swap(a[parent], a[child]);parent child;child parent * 2 1;}else {break;}}
}//升序建大堆 降序建小堆
void HeapSort(int* a, int n) {//建堆从倒数第一个父节点开始向前遍历向下调整for (int i (n-1-1)/2; i 0 ;i--) {AdjustDown(a,n,i);}//先将首尾元素进行交换再向下调整while (n - 1) {swap(a[0], a[n - 1]);AdjustDown(a, n-1,0);n--;}
}int main() {int a[7] { 2,6,5,1,7,4,3 };int n sizeof(a) / sizeof(a[0]);HeapSort(a, n);for (int i 0; i n; i) {printf(%d ,a[i]);}return 0;
}
从时间复杂度角度分析建堆为何采取向下调整
下面将分别分析向下调整算法建堆和向上调整算法建堆的区别
向下调整建堆 假设节点数量为N,树的高度为h
第一层2^0个节点需要向下调整h-1层
第二层2^1个节点需要向下调整h-2层
第三层2^2个节点需要向下调整h-3层
……
第h层2^h个节点需要向下调整0层
可以看出节点少的层向下调整得多节点多的层向下调整得少
计算向下调整建堆最坏情况下合计的调整次数 通过错位相减法可得 因此向下调整建堆的时间复杂度为O(N
向上调整建堆 假设节点数量为N,树的高度为h
第一层2^0个节点需要向下调整0层
第二层2^1个节点需要向下调整1层
第三层2^2个节点需要向下调整2层
……
第h层2^h个节点需要向下调整h-1层
可以看出节点少的层向上调整得少节点多的层向上调整得多。
T(h)2^1*12^2*2……2^(h-2)*(h-2)2^(h-1)*(h-1)
同样由错位相减法可得
T(h)-(2^22^3……2^h-1)2^h*(h-1)-2^1
整理可得
T(N)-N(N1)*(log2(N1)-1)1
因此向上调整建堆的时间复杂度为ON*logN
所以我们选择向下建堆算法明显效率更高。
