当前位置：首页 > news >正文

数据结构：堆的算法

news 来源：原创 2024/9/22 5:36:12

一堆的向上调整算法

我们在堆中插入一个数据一般实在堆的最后插入然后可以一步一步与上层结点（父结点进行比较），继而进行交换，完成二叉树的结构，

在这里插入图片描述
其中我们就有公式父节点的下标=（孩子结点的下标-1）/2就等价于parent=（child-1）/2

我们可以写一个方法让插入的数据与父结点进行比较直到合适的位置为止。

那么停下来就有两种情况：
1一直交换到头结点停下。2交换到合适的位置但没有到头结点，中途停下。

第一种情况一直到头结点，因为每次都要

child=parent;
parent = (child - 1) / 2;

所以当child到0没有父结点了就循环结束。

void AdjustUp(HeapType* 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;}}}void Swap(HeapType* a, HeapType* b) {HeapType* tem = *a;*a = *b;*b = tem;}

第二种情况因为中点调整好了当if语句没交换时候就可以结束循环调整完成了

加上else
{
break;
}

void AdjustUp(HeapType* 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;}}}

二堆的向下调整算法

当我们要去删除一个大堆或者小堆的头结点的时候我们可以直接把尾部结点的数据和头部的交换，然后把访问下标的数字-1.然后进行向下调整，这样就可以建立二叉树的结构了

但是我们有一个问题，我们都知道parent=(child-1)/2，且有唯一一个父节点。但是我们让头结点进行向下调整的时候要去交换哪个孩子结点呢？是否要判断?

在这里插入图片描述

如图这是个小堆，头结点进行向下调整的时候需要判断跟哪个孩子交换，必须保证是次小的孩子，要不然就会出现父节点比孩子结点大，就不是小堆了。大堆也是同样道理

判断代码如下

if (child + 1 < n && a[child] > a[child + 1]) {child = child + 1;

其中n是有效数据个数，需要保证有两个孩子才能判断
向下调整算法代码如下

void AdjustDown(HeapType* a, int parent, int n) {int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] > a[child + 1]) {child = child + 1;}if (a[parent] > a[child]) {Swap(&a[parent], &a[child]);parent = child;child = child * 2 + 1;}else{break;}}}

三堆的应用:堆排序

那么我们可以通过堆的结构来进行排序，因为二叉树不是严格意义上的顺序结构它只保证父节点比孩子结点大或小。
我们可以实现一个算法来把堆的二叉树结构调整为升序或者降序。

具体实现方法为，循环把头结点和尾结点进行交换，因为头结点是一个结构最大或者最小的，这时候我们把尾部结点减少一个，在进行向下调整，然后再进行交换，把次大或次小的数据放到最后一个，尾部结点减少一个，向下调整…如此循环直到到最后一个数据向下调整。这样就变成有序的了。
因为大堆的头结点是最大的，一开始放到尾结点，这样就是升序，反之小堆调整则为降序。

HeapSort2(a1, 6);
int sz = sizeof(a1) / sizeof(a1[0]);
for (int i = 0; i < sz; i++) {printf("%d ",a1[i]);
}
void HeapSort2(HeapType* arr, int n) {//进行向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--) {AdjustDown(arr, i, n);}int end = n - 1;for (int i = end; i > 0; i--) {//小堆进行调整为降序Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}

在这里插入图片描述

四TOPK问题

我们在N个数据中找前topk大或者小的数据这类问题一般思路就是一个个进行比较，这样空间复杂度太大。

我们可以先建立一个大小为k的堆，然后通过后N-k个数据依次和堆的头结点进行比较，判断是否入堆，如果入堆就向下调整到合适位置，这样数据读完我们就可以销毁文件，那么空吉安复杂度则只有建立的堆，然后堆的数据即为topk.

我们可以进行文件输入输出流来实现创造 N个数据
中间利用time函数，利用写的方式把数据写道date,txt文件中
大小为不大于等于1000000

void CreateNDate()
{// 造数据int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}

然后读取数据，建立k个大小的堆，再把文件后面数据和堆顶比较，如果比堆顶大就进堆，然后向下调整。

void PrintTopK() {int k = 0;printf("请输入");scanf("%d",&k);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL) {perror("error");}HeapType* pp = (HeapType*)malloc(k * sizeof(HeapType));for (int i = 0; i < k; i++) {fscanf(fout, "%d", &pp[i]);}for (int i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(pp, i, k);}int x=0;while (fscanf(fout, "%d", &x) != EOF) {if (x > pp[0]) {pp[0] = x;AdjustDown(pp, 0, k);}}for (int i = 0; i < k;i++)  {printf("%d ", pp[i]);}fclose(fout);}