ACM大牛带你玩转算法与数据结构-课程资料
本笔记属于船说系列课程之一，课程链接：
哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep66799?csource=private_space_class_null&spm_id_from=333.999.0.0
你也可以选择购买『船说系列课程-年度会员』产品『船票』，畅享一年内无限制学习已上线的所有船说系列课程：船票购买入口
做题网站OJ：HZOJ - Online Judge
Leetcode :力扣 (LeetCode) 全球极客挚爱的技术成长平台
前置普通建堆：数据结构——堆
线性建堆法
普通建堆法的时间复杂度度是O(nlogn)，而线性键堆法的时间复杂度是O(n)的。
普通建堆法是通过向上调整的，应为每次它添加一个元素都是添加在堆的末尾，然后通过一步一步的向上调整，而这个过程的时间复杂度就是n(logn)为什么是log(n)，二叉树的高度约等于log(n)，那么它每次调整都是向上层调整一次，所以就需要调整约logn次，那么需要添加n个元素，那么它的时间复杂度就为n * logn。
而线性建堆法是通过向下调整的
比如：
现在有一个数组
将它模拟成二叉树的模样：
现在需要一个大顶堆，让后采用线性建堆法，也就是向下调整，从最下面有子节点的节点开始调整：
现在就是从倒数第二层开始调整：
然后再在向上一层就是根节点的位置：
整个过程只用了4次调整，而普通键堆方法需要用7次，就用这个数组可以去自己去试一下。
线性键堆法的时间复杂度：
现在假如有一颗完全二叉树，他的高度有k。
这样可以推算出线性建堆法的时间复杂度为O(n)为常量级别的。
下面是线性键堆法的代码演示：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define swap(a, b) {\
__typeof(a) __a = (a);\
(a) = (b);\
(b) = __a;\
}
int *getNewData(int n) {
int *arr = (int *)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) arr[i] = rand() % 1000;
return arr;
}
void down_updata(int *, int, int);
//堆排序
void heap_sort(int *data, int n) {
for (int i = n; i >= 1; i--) {
swap(data[1], data[i]);
down_updata(data, 1, i - 1);
}
return ;
}
void down_updata(int *data, int i, int n) {
while ((i << 1) <= n) {
int ind = i, l = i << 1, r = (i << 1) + 1;
if (data[l] > data[ind]) ind = l;
if (r <= n && data[r] > data[ind]) ind = r;
if (i == ind) break;
swap(data[i], data[ind]);
i = ind;
}
return ;
}
void line_bulid_pq(int *data, int n) {
for (int i = n / 2; i >= 1; i--) {
down_updata(data, i, n);
}
}
//线性键堆法
void line_pq(int *arr, int n) {
int *data = arr - 1;
line_bulid_pq(data, n);
heap_sort(data, n);
}
int check(int *arr, int n) {
for (int i = 1; i < n; i++) {
if (arr[i] < arr[i - 1]) return 0;
}
return 1;
}
void output(int *arr, int n) {
if (!check(arr, n)) {
printf("is fail\n");
return ;
}
for (int i = 0; i < n; i++) {
i && printf(" ");
printf("%d", arr[i]);
}
putchar(10);
return ;
}
int main() {
srand(time(0));
#define MAX_N 100
int *arr = getNewData(MAX_N);
line_pq(arr, MAX_N);
output(arr, MAX_N);
return 0;
}
