网站建设分项报价表,社交型网站首页面设计分析,汕头企业免费建站,wordpress page页面文章目录堆的实现堆向下调整算法堆的创建堆的插入堆的删除堆的代码实现堆的应用堆的实现
堆是属于操作系统进程地址空间内存区域的划分。
我们下面实现数据结构中的堆。 堆是一个完全二叉树#xff1a;分为小根堆和大根堆。 小根堆#xff1a;任何一个节点的值都孩子的…
文章目录堆的实现堆向下调整算法堆的创建堆的插入堆的删除堆的代码实现堆的应用堆的实现
堆是属于操作系统进程地址空间内存区域的划分。
我们下面实现数据结构中的堆。 堆是一个完全二叉树分为小根堆和大根堆。 小根堆任何一个节点的值都孩子的值
大根堆任何一个节点的值都孩子的值 应用 1.堆排序第一个时间复杂度达到–O(N*log N)的排序。 2.topK问题找一堆数据前K大或者前K小。
数组下标计算父子关系公式
左孩子leftchild parent*2 1 右孩子rightchild parent*2 2 孩子算父亲parent (child - 1) / 2
堆向下调整算法
给出一个数组逻辑上看做一颗完全二叉树。通过从根节点开始的向下调整算法可以把它调整成一个小堆。 前提左右子树必须是一个堆才能调整。
int array[] {27,15,19,18,28,34,65,49,25,37};堆的创建
给出一个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们把它构建成一个堆。根节点左右子树不是堆这里我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆。 采用向下调整建堆。
int a[] {1,5,3,8,7,6}; 堆的插入
先插入一个数组的尾上再进行向上调整算法直到满足堆。
1.先将元素插入到对的末尾即最后一个孩子之后。 2.插入之后如果堆的性质遭到了破坏将新插入节点顺着双亲往上调整到合适位置即可。 AdjustUp
堆的删除
删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。
1.将堆顶元素与堆中追后一个元素进行交换。 2.删除堆中最后一个元素 3.将堆顶元素向下调整到满足堆特性为止。 堆的代码实现 heap.h #pragma once#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void HeapPrint(HP* php);void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);void HeapInit(HP* php);
void HeapDestroy(HP* php);
// xֶ̬
void HeapPush(HP* php, HPDataType x);
// ɾѶԪ
void HeapPop(HP* php);
// ضѶԪ
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);Heap.c #include Heap.hvoid HeapPrint(HP* php)
{for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}void HeapInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-capacity php-size 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;//while (parent 0)while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}// 插入x继续保持堆形态 -- logN
void HeapPush(HP* php, HPDataType x)
{assert(php);// 扩容if (php-size php-capacity){int newCapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, newCapacity*sizeof(HPDataType));if (tmp NULL){perror(realloc fail);exit(-1);}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}void AdjustDown(HPDataType* a, int n, int parent)
{int minChild parent * 2 1;while (minChild n){// 找出小的那个孩子if (minChild1 n a[minChild 1] a[minChild]){minChild;}if (a[minChild] a[parent]){Swap(a[minChild], a[parent]);parent minChild;minChild parent * 2 1;}else{break;}}
}// 删除堆顶元素 -- 找次大或者次小 -- logN
// O(logN)
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}// 返回堆顶的元素
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php-a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}int HeapSize(HP* php)
{assert(php);return php-size;
}堆的应用 堆排序 1.建堆: 升序建大堆 降序建小堆 2.利用堆删除思想来进行排序
int a[] {201741653}; 建堆和堆删除中都用到了向下调整因此必须掌握了向下调整。
