营销导向的网站建设的主要流程,装饰工程,wordpress视频存储,网站建设山东聚搜网络目录
一#xff0c;堆
堆的概念
向下调整法#xff08;数组#xff09;
向上调整法#xff08;数组#xff09;
堆的创建#xff08;建堆#xff09;
堆的实现 一#xff0c;堆 堆的概念
如有个关键码的集合K{#xff0c;#xff0c;#xff0c;...#xf…目录
一堆
堆的概念
向下调整法数组
向上调整法数组
堆的创建建堆
堆的实现 一堆 堆的概念
如有个关键码的集合K{...}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足 且 ( 且 )i0、1、...则称为小堆(大堆)
小堆 且 即所有节点小于等于孩子根节点最小叫做最小堆或小根堆
大堆 且 即所有节点大于等于孩子根节点最大叫做最大堆或大根堆
堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值根一定是最值最大值或最小值堆总是一颗完全二叉树适合顺序结构存储
向下调整法数组
将数组看做为一颗完全二叉树可使用向下调整法创建堆前提条件为此二叉树的左右子树需是一个堆只有根节点不满足堆要求从根开始与左右子节点中的最小值比较并交换依次类推直到比父亲大或到叶子节点终止时间复杂度O(logN)注向上调整法类似
int array[] {27,15,19,18,28,34,65,49,25,37}; //向下调整法小堆
void Swap(int* px, int* py)
{int tmp *px;*px *py;*py tmp;
}void AdjustDown(int* arr, int n, int parent)
{int child 2 * parent 1;//无孩子节点或父亲小于孩子即终止while (child n){if (child 1 n arr[child 1] arr[child])child;if (arr[parent] arr[child]){Swap(arr parent, arr child);parent child;child 2 * parent 1;}elsebreak;}
}
向上调整法数组
//向上调整法
void AdjustUp(int* arr, int child)
{int parent (child - 1) / 2;//大堆//根节点或父亲大于孩子即终止while (child 0){if (arr[parent] arr[child]){Swap(arr parent, arr child);child parent;parent (child - 1) / 2;}elsebreak;}
}
堆的创建建堆 即对数据如数组可看为完全二叉树将其构建为堆方法为从倒数第一个非叶子节点的子树开始调整直到根节点为止即每次调整时使用向下调整法建堆时间复杂度O(N)下面有证明注也可使用向上调整法建堆但初始化堆的个别元素位置可能不一样
int arr[] {1,5,3,8,7,6};
//建堆-向下调整法
void Heap(int* arr, int n)
{int i (n - 1 - 1) / 2; //最后节点的父节点for (i; i 0; i--){AdjustDown(arr, n, i);}
}
//建堆-向上调整法
void Heap(int* arr, int n)
{int i 1; for (i; i n; i){AdjustUp(arr, i);}
} 建堆时间复杂度 堆排序
升序建大堆将最大的数换到最后在将剩下的数向下调整下选出次大数依次类推降序建小堆将最小的数换到最后在将剩下的数向下调整下选出次小数依次类推整体的时间复杂度O(N*logN)如升序建小堆(或降序建大堆)的话选出最值后需在继续建堆(O(N))效率较低还不如直接遍历建堆的价值未体现
//建堆排序
void HeapSort(int* arr, int n)
{//建堆 - O(N)int i (n - 1 - 1) / 2; //最后节点的父节点for (i; i 0; i--){AdjustDown(arr, n, i);}//排序 - O(N*log(N))int end n - 1;while (end){Swap(arr, arr end);AdjustDown(arr, end, 0);end--;}
} 堆的实现
//堆
typedef int HPDataType;typedef struct Heap
{HPDataType* data;int size;int capacity;
}Heap;//初始化
void HeapInit(Heap* php, HPDataType* arr, int n);//释放销毁
void HeapDestroy(Heap* php);//插入数据并保持堆
void HeapPush(Heap* php, HPDataType* x);//删除堆顶数据并保持堆
void HeapPop(Heap* php);//返回堆顶数据
HPDataType HeapTOP(Heap* php);//返回堆节点个数
int HeapSize(Heap* php);//判断释放为空
bool HeapEmpty(Heap* php);注完整接口实现代码路径https://gitee.com/napoleoncode/start-code/tree/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/06_Heap
TOP-K问题
直接排序O(N*log(N))建个N个数的堆并取出前K个数O(NK*log(N))建个K个数的小堆然后将剩下的数依次与堆顶比较大即入堆最后此堆即为最大的K个数O(N*log(K))(如N非常大内存不够前两种方法即适用了)注通常K远小于N
//TOP-K
void TOPK(int* arr, int n, int k)
{Heap hp;//建堆HeapInit(hp, arr, k);int i k;for (i; i n; i){//替换if (HeapTop(hp) arr[i]){HeapPop(hp);HeapPush(hp, arr[i]);}}HeapPrint(hp);HeapDestroy(hp);
}
