dede网站模板 音响,海外酒店 网站建设,wordpress 4.8 语言,产品报价网一、堆的概念及结构
1、概念 堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵 完全二叉树的 数组对象。 堆是非线性数据结构#xff0c;相当于一维数组#xff0c;有两个直接后继。 如果有一个关键码的集合K { k₀#xff0c;k₁#xff0c…一、堆的概念及结构
1、概念 堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵 完全二叉树的 数组对象。 堆是非线性数据结构相当于一维数组有两个直接后继。 如果有一个关键码的集合K { k₀k₁k₂ k₃ …kₙ₋₁ }把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足Kᵢ K₂ *ᵢ₊₁ 且 Kᵢ K₂ *ᵢ₊₂ (Kᵢ K₂ *ᵢ₊ ₁ 且 Kᵢ K₂ *ᵢ₊₂ ) i 012…则称为小堆 (或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 【大根堆和小根堆】 根结点最大的堆叫做大根堆树中所有父亲都大于或等于孩子。 根结点最小的堆叫做小根堆树中所有父亲都小于或等于孩子。 这个大根堆和小根堆有什么特点呢 最值总在 0 号位根据这个特点我们可以做很多事情。比如 TopK 问题 (在一堆数据里面找到前 K 个最大 / 最小的数)。生活中也有很多实例比如某外卖软件中有上千家店铺我想选出当地好评最多的十家烤肉店这时我们不用对所有数据进行排序只需要取出前 K 个最大 / 最小数据。使用堆排序效率也更高。 2、性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树。 二、堆的实现
1、堆向下调整算法 给出一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的 向下调整算法 可以把它调整成一个 小堆 。向下调整算法有一个前提左右子树必须是一个堆包括大堆和小堆 才能调整。 从根节点开始不断往下调。选出根节点的左右孩子中小的那个孩子再与父亲进行比较。(1)如果父亲小于孩子就不需处理了整个树已经是小堆了。(2) 如果父亲大于孩子就跟父亲交换位置并将原来小的孩子的位置当成父亲继续向下进行调整直到调整到叶子结点为止。 int array[] {27,15,19,18,28,34,65,49,25,37}; // 根节点的左右子树都是小堆 // 向下调整算法 -- 调成小堆把大的节点往下调整
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){// 判断右孩子是否存在 选出左右孩子中小的那个if (child 1 size a[child 1] a[child]){child;}// 孩子跟父亲比较if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
【时间复杂度】我们以满二叉树计算最坏情况下向下调整算法最多进行满二叉树的高度减 1 次比较则说明向下调整算法最多调整满二叉树的高度减 1 次n 个节点的满二叉树高度为 log₂(n1)估算后所以时间复杂度为 O(log₂n)。 2、堆的创建 给出一个数组这个数组逻辑上可以看做一颗完全二叉树但还不是一个堆现在我们可以通过算法把它构建成一个堆。根节点左右子树不是堆我们怎么调整呢我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆。 为什么要倒着调整呢 因为这样我们可以把倒数第一个非叶子节点的子树的左右子树看成是一个 (大 / 小) 堆满足向下调整的前提条件这时才能去使用向下调整算法。 // 建大堆
int a[] {1,5,3,8,7,6}; 建堆过程演示以建大堆为例从下到上依次遍历完所有非叶子节点分别对每个子树进行向下调整。依次进行每一步方框内的树进行向下调整为一个大堆。 调换 1 和 8 的位置时8 的其左子树构成的递归结构被破坏。因此在每一次发生元素交换时都需要递归调用重新构造堆的结构。 #include stdio.h
#include stdlib.hvoid Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}// 向下调整算法 -- 建大堆把小的节点往下调整
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){// 判断右孩子是否存在 选出左右孩子中大的那个if (child 1 size a[child 1] a[child]){child;}// 孩子跟父亲比较if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}// 升序 -- 建大堆 -- 每次选出一个最大的数放到最后
// 降序 -- 建小堆 -- 每次选出一个最小的数放到最后
// 堆排序 -- 效率更高
void HeapSort(int* a, int n)
{// O(N)// botto-top(自底向上)依次遍历完所有子树分别对其进行调整for (int i((n-1)-1)/2; i0; i--) // 从最后一个叶子节点的父亲的下标开始{AdjustDown(a, n, i);}// 升序// O(N*logN)int end n - 1; // 记录堆中最后一个元素的下标while (end 0){Swap(a[0], a[end]); // 将堆顶元素和堆中最后一个元素交换把最大的数(堆顶)放到最后AdjustDown(a, end, 0);--end;}
} 【拓展】堆的创建采用向上调整法
下面给出一个数组这个数组逻辑上可以看做一颗完全二叉树但不是一个堆我们需要通过向上调整算法把它构建成一个堆。如果根节点左右子树不是一个 (大 / 小) 堆我们应该怎么调整呢 我们从上到下从第一个节点也就是根节点的左孩子开始依次遍历完所有节点分别对每个节点进行向上调整一直到最后一个节点就可以建成一个 (大 / 小) 堆。 我们把数组中的第一个元素看作是一个堆剩余的元素依次插入到这个堆中。这跟堆的插入接口原理相同就是向上调整。 如果堆的创建过程使用向上调整算法那么每次插入一个新元素时都需要进行一次向上调整操作以确保新插入的元素能够满足堆的性质。 【时间复杂度】 假设堆中已经有 n 个元素那么堆的高度 h log₂(n1)在插入一个新元素的过程中需要进行的向上调整操作次数为 h-1则 h log₂(n1) - 1该操作的时间复杂度为O(log₂n)。需要注意的是这个时间复杂度是针对单次 “向上建堆” 操作而言的。如果需要对一个无序数组进行完整的堆排序则需要进行 n/2 次 “向上建堆” 操作那么整个堆排序的时间复杂度为 O(nlog n)。所以如果使用向上调整算法来创建堆排序那么堆的创建过程的时间复杂度为 O(n*log₂n)。 结论 使用向上调整算法创建堆需要进行多次调整操作而使用向下调整算法只需要进行一次调整操作。因此从实际操作的角度来看使用向下调整算法创建堆更为高效。同时向下调整算法也更为直观容易理解和实现。因此在实际应用中一般会选择使用向下调整算法来创建堆。 【堆排序】 利用 堆删除 思想来进行排序后文有介绍 建堆和堆删除中都用到了 向下调整 因此掌握了向下调整就可以完成堆排序。 1升序 -- 建大堆 【思考】排升序建小堆可以吗-- 可以但不推荐。 ⚪首先对 n 个数建小堆选出最小的数接着对剩下的 n-1 个数建小堆选出第2小的数不断重复上述过程。 【时间复杂度】建 n 个数的堆时间复杂度是 O(N)所以上述操作时间复杂度为 O(N²)效率太低尤其是当数据量大的时候效率就更低。同时堆的价值也没有被体现出来这样不如用直接排序。 ⚪【最佳方法】排升序因为数字依次递增需要找到最大的数字得建大堆。 首先对 n 个数建大堆。将最大的数堆顶和最后一个数交换把最大的数放到最后。前面 n-1 个数的堆结构没有被破坏最后一个数不看作在堆里面的根节点的左右子树依然是大堆所以我们进行一次向下调整成大堆即可选出第 2 大的数放到倒数第二个位置然后重复上述步骤。 【时间复杂度】建堆时间复杂度为 O(N)向下调整时间复杂度为 O(log₂N)这里我们最多进行N-2 次向下调整所以堆排序时间复杂度为 O(N*log₂N)效率相较而言是很高的。 2降序 -- 建小堆与建大堆同理 【最佳方法】排降序因为数字越来越小需要找到最小的数字得建小堆。 首先对 n 个数建小堆。将最小的数堆顶和最后一个数交换把最小的数放到最后。前面 n-1 个数的堆结构没有被破坏最后一个数不看做堆里面的根节点的左右子树依旧是小堆所以我们进行一次向下调整成小堆即可选出第2小的数放到倒数第二个位置然后重复上述步骤。 【时间复杂度】建堆时间复杂度为 O(N)向下调整时间复杂度为 O(log₂N)这里我们最多进行N-2 次向下调整所以堆排序时间复杂度为O(N*log₂N)效率相较而言是很高的。 3、建堆时间复杂度 因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个节点不影响最终结果) 等比数列求和公式 建堆要从倒数第一个非叶子节点开始调整也即是从倒数第二层开始调可得出时间复杂度公式 T ( n ) ∑ ( 每 层 节 点 数 ∗ ( 堆 的 高 度 − 当 前 层 数 ) ) 建堆的时间复杂度为O(N)。向下调整算法 4、堆的插入 先插入一个 10 到数组的尾上再进行 向上调整算法 直到满足堆。 5、堆的删除 删除堆是删除堆顶的数据 将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行 向下调整算法 。 将堆顶元素和最后一个元素交换这样就变成尾删了。删除堆中最后一个元素。从根节点开始对剩下元素进行向下调整调成大 / 小堆。 6、堆的代码实现
1文件的创建 test.c主函数、测试堆各个接口功能Heap.c堆接口函数的实现Heap.h堆的类型定义、接口函数声明、引用的头文件 2Heap.h 头文件代码
// Heap.h
#pragma once#include stdio.h
#includestdlib.h // malloc, free
#include assert.h // assert
#include stdbool.h // bool
#includestring.h // memcpytypedef int HPDataType;typedef struct Heap
{HPDataType* a; // 指向动态开辟的数组int size; // 数组中有效元素个数int capacity; // d容量
}Heap;// 交换函数
void Swap(HPDataType* p, HPDataType* q);
// 向下调整函数调成大堆把小的往下调
void AdjustDown(HPDataType* a, int size, int parent);
// 向上调整函数调成大堆把大的往上调
void AdjustUp(HPDataType* a, int child);
// 堆的打印
void HeapPrint(Heap* hp);// 堆的构建
void HeapCreate(Heap* hp, HPDataType* arr, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp); 3接口的实现以大堆为例
I.堆的创建初始化 堆的初始化一般是使用数组进行初始化的还需要先实现一个向下调整算法。 //交换
void Swap(HPDataType* p, HPDataType* q)
{HPDataType tmp *p;*p *q;*q tmp;
}// 向下调整调成大堆把小的往下调
void AdjustDown(HPDataType* a, int size, int parent)
{int child parent * 2 1;while (child size){//选出左右孩子中大的那个if (child 1 size a[child 1] a[child]){child;}//孩子跟父亲比较if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}// 堆的构建
void HeapCreate(Heap* hp, HPDataType* arr, int n)
{assert(hp);//断言hp-a (HPDataType*)malloc(sizeof(HPDataType) * n);//动态开辟n个空间if (hp-a NULL){printf(malloc fail\n);exit(-1);}memcpy(hp-a, arr, sizeof(HPDataType) * n);//把给定数组的各元素值拷贝过去hp-size hp-capacity n;//建堆建大堆int parent ((hp-size - 1) - 1) / 2; //倒数第一个非叶子节点下标for (int i parent; i 0; i--){AdjustDown(hp-a, hp-size, i);}
} II.堆的打印
// 打印
void HeapPrint(Heap* hp)
{assert(hp);for (int i 0; i hp-size; i){printf(%d , hp-a[i]);}printf(\n);
} III.堆的销毁
// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);free(hp-a); // 释放动态开辟的空间hp-a NULL;hp-size hp-capacity 0;
} IV.堆的插入 堆的插入数据不分头插、尾插。将数据插入后原来堆的属性不变。先放在数组的最后一个位置再进行向上调整。堆的插入首先需要实现一个向上调整算法。 //向上调整调成大堆把大的往上调
void AdjustUp(HPDataType* 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;}// 如果孩子小于父亲说明已经为大堆了停止调整else{break;}}
}// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp-size hp-capacity){int newcapacity hp-capacity 0 ? 4 : (hp-capacity) * 2;HPDataType* tmp (HPDataType*)realloc(hp-a, sizeof(HPDataType) * newcapacity);if (tmp NULL){printf(realloc fail\n);exit(-1);}hp-a tmp;hp-_capacity newcapacity;}// 插入元素hp-a[hp-size] x;hp-size;AdjustUp(hp-a, hp-size - 1); // 从插入的元素开始进行向上调整保持它依然是堆
} 注意这里的 while 括号里的条件不能写成 (parent 0)因为 parent 在这里不会小于 0。假设child 为 0则 parent (0-1) / 2 0。 V.堆的删除 删除堆顶元素删除后保持它依然是堆。 // 堆的删除
void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp)); // 堆不能为空Swap((hp-a[0]), (hp-a[hp-size - 1])); // 将堆顶元素和最后一个元素交换hp-size--; // 删除堆中最后一个元素// 从根节点开始对剩下元素进行向下调整成大堆保持它依然是堆AdjustDown(hp-a, hp-size, 0);
} VI.取堆顶元素
// 取堆顶的数据最值
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp)); // 堆不能为空return hp-a[0];
} VII.堆的数据个数
// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp-size;
} VIII.堆的判空 判断堆是否为空为空返回true不为空返回false。 // 堆的判空
bool HeapEmpty(Heap* hp)
{assert(hp);return hp-size 0;
} 4代码整合
// Heap.c
#include Heap.h//交换
void Swap(HPDataType* p, HPDataType* q)
{HPDataType tmp *p;*p *q;*q tmp;
}// 打印
void HeapPrint(Heap* hp)
{assert(hp);for (int i 0; i hp-size; i){printf(%d , hp-a[i]);}printf(\n);
}// 向下调整调成大堆把小的往下调
void AdjustDown(HPDataType* a, int size, int parent)
{int child parent * 2 1;while (child size){//选出左右孩子中大的那个if (child 1 size a[child 1] a[child]){child;}//孩子跟父亲比较if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}//向上调整调成大堆把大的往上调
void AdjustUp(HPDataType* 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;}// 如果孩子小于父亲说明已经为大堆了停止调整else{break;}}
}// 堆的构建
void HeapCreate(Heap* hp, HPDataType* arr, int n)
{assert(hp);//断言hp-a (HPDataType*)malloc(sizeof(HPDataType) * n);//动态开辟n个空间if (hp-a NULL){printf(malloc fail\n);exit(-1);}memcpy(hp-a, arr, sizeof(HPDataType) * n);//把给定数组的各元素值拷贝过去hp-size hp-capacity n;//建堆建大堆int parent ((hp-size - 1) - 1) / 2; //倒数第一个非叶子节点下标for (int i parent; i 0; i--){AdjustDown(hp-a, hp-size, i);}
}// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);free(hp-a); // 释放动态开辟的空间hp-a NULL;hp-size hp-capacity 0;
}// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp-size hp-capacity){int newcapacity hp-capacity 0 ? 4 : (hp-capacity) * 2;HPDataType* tmp (HPDataType*)realloc(hp-a, sizeof(HPDataType) * newcapacity);if (tmp NULL){printf(realloc fail\n);exit(-1);}hp-a tmp;hp-_capacity newcapacity;}// 插入元素hp-a[hp-size] x;hp-size;AdjustUp(hp-a, hp-size - 1); // 从插入的元素开始进行向上调整保持它依然是堆
}// 堆的删除
void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp)); // 堆不能为空Swap((hp-a[0]), (hp-a[hp-size - 1])); // 将堆顶元素和最后一个元素交换hp-size--; // 删除堆中最后一个元素// 从根节点开始对剩下元素进行向下调整成大堆保持它依然是堆AdjustDown(hp-a, hp-size, 0);
}// 取堆顶的数据最值
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp)); // 堆不能为空return hp-a[0];
}// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp-size;
}// 堆的判空
bool HeapEmpty(Heap* hp)
{assert(hp);return hp-size 0;
} 5程序运行效果 三、堆的应用
【TOP-K问题】 TOP-K 问题即求数据结合中前 K 个最大的元素或者最小的元素一般情况下数据量都比较大。 在生活中也有不少例子班级前 10 名、世界 500 强、富豪榜等。 方法一对于 Top-K 问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了可能数据都不能一下子全部加载到内存中。 排序 --【时间复杂度为】O(N*logN)。 方法二建一个 N 个数的堆(优先级队列)不断选数选出前 K 个。 【时间复杂度】 O(NK*log(N)) 假设 N 是十亿显然前两个方法都不适用。 【最佳方法】-- 方法三最佳的方式就是用堆来解决基本思路如下 1、用数据集合中前 K 个元素来建堆。 前k个最大的元素则建小堆 前k个最小的元素则建大堆 2、用剩余的 N-K 个元素依次与堆顶元素来比较不满足则替换堆顶元素。将剩余 N-K 个元素依次与堆顶元素比完之后堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。 // test.c
#include stdio.h
#include stdlib.h
#include assert.h
#include time.hvoid PrintTopK(int* a, int n, int k)
{// 1、建堆 -- 用a中前k个元素建堆(0~k-1)int* kMinHeap (int*)malloc(sizeof(int) * k);assert(kMinHeap);for (int i 0; i k; i){kMinHeap[i] a[i];}for (int i (k - 1 - 1) / 2; i 0; --i){AdjustDown(kMinHeap, k, i);}// 2、将剩余n-k个元素依次与堆顶元素交换不满则则替换(k~n)for (int j k; j n; j){if (a[j] kMinHeap[0]){kMinHeap[0] a[j];AdjustDown(kMinHeap, k, 0);}}for (int i 0; i k; i){printf(%d , kMinHeap[i]);}printf(\n);
}void TestTopk()
{int n 10000;int* a (int*)malloc(sizeof(int) * n);// 创建随机数种子srand((unsigned int)time(0));for (int i 0; i n; i){a[i] rand() % 1000000; // 生成随机数}// 如果找出这10个数说明TOP-K算法是正确的a[5] 1000000 1;a[1231] 1000000 2;a[531] 1000000 3;a[5121] 1000000 4;a[120] 1000000 5;a[99] 1000000 6;a[0] 1000000 7;a[76] 1000000 8;a[423] 1000000 9;a[3144] 1000000 10;PrintTopK(a, n, 10);
}
