目录
堆的概念及结构
编辑
堆的实现
实现堆的接口
堆的初始化
堆的打印
堆的销毁
获取最顶的根数据
交换
堆的插入(插入最后)
向上调整(这次用的是小堆)
堆的删除(删除根)
向下调整(这次用的小堆)
堆排序
TOP-K问题
堆的概念及结构
- 堆中某个节点的值总是不大于或不小于其父节点的值;
- 堆总是一棵完全二叉树。
小根堆:父亲节点大于等于孩子节点
大根堆:父亲节点小于等于孩子节点
堆的实现
实现堆的接口
#define CRT_SECURE_NO_WARNING 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<stdbool.h>
//二叉树-堆
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
//交换
void Swap(HPDataType* p1, HPDataType* p2);
//打印
void HeapPrint(HP* php);
//初始化
void HeapInit(HP* php);
//
void HeapInitArray(HP* php, int* a, int n);
//销毁
void HeapDestroy(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//删除
void HeapPop(HP* php);
//返回最顶数据
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);
堆的初始化
//初始化
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
堆的打印
void HeapPrint(HP* php)
{
assert(php);
//最后一个孩子下标为size-1
for (size_t i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
堆的销毁
//销毁
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
获取最顶的根数据
//获取根数据
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
交换
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
堆的插入(插入最后)
先考虑扩容,将数据插到最后,再用向上调整法。
//插入数据
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//扩容
if (php->size == php->capacity)//有效元素个数和容量是否相等
{
//相等的情况分两种:1.容量为0,先扩4个sizeof 2.容量占用满了,扩2个
int newCapacity =php->capacity == 0 ? 4 : php->capacity * 2;
//返回扩容后的内存新地址 //扩容后的新大小
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
//扩容后的新地址
php->a = tmp;
//新容量
php->capacity = newCapacity;
}
// php->size下标位置 先将x放最后,后面再调整
php->a[php->size] = x;
// 有效数据++
php->size++;
// 向上调整 //size-1为新插入数据的下标
AdjustUp(php->a, php->size - 1);
}
向上调整(这次用的是小堆)
向上调整的前提:左右子树是堆 ,时间复杂度O(logN)
//向上调整 //新插入的数据下标
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 = (parent - 1) / 2;
}
else
{
break;
}
}
}
堆的删除(删除根)
先判空,看下是否还有元素可以删除。根数据先和最后一个孩子交换位置,孩子再向下调整。
//删除
void HeapPop(HP* php)
{
assert(php);
//确保有元素可删
assert(php->size > 0);
//最后一个孩子和要删除的根交换
Swap(&php->a[0], &php->a[php->size - 1]);
//有效元素size减减,相当于删除了交换后的原来的根
--php->size;
//删除后向下调整
AdjustDown(php->a, php->size, 0);
}
向下调整(这次用的小堆)
向下调整的前提:左右子树是堆
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
//n下标位置已经没有数了
while (child < n)
{
//选小的孩子往上浮(小堆)
if (child + 1 < n && a[child + 1] < a[child])
{
++child;
}
//若小的孩子都小于父,则交换
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//交换后下来的数重新变成parent,继续向下调整
parent = child;
child = parent * 2 + 1;
}
}
}
堆排序
void HeapSort(int* a, int n)
{
//建堆 这里可以选建大堆还是小堆
// 向下调整建堆
// O(N)
for (int i = (n-1-1)/2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
TOP-K问题
先创建一个包含有10000000个数的data.txt文本文件。
void CreateNDate()
{
// 造数据
int n = 10000000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = (rand() + i) % 10000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
前k个建小堆(堆顶元素为k中最小),剩余n-k个依次和堆顶元素比较,比k大就插入堆中(插入堆插入向下调整法),完成后打印前k个元素。
void PrintTopK(const char* filename, int k)
{
// 1. 建堆--用a中前k个元素建堆
FILE* fout = fopen(filename, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
//给堆开辟空间
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
perror("malloc fail");
return;
}
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minheap[i]);
}
// 前k个数建小堆
for (int i = (k - 2) / 2; i >= 0; --i)
{
AdjustDown(minheap, k, i);
}
// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
if (x > minheap[0])
{
// 替换你进堆
minheap[0] = x;
AdjustDown(minheap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minheap[i]);
}
printf("\n");
free(minheap);
fclose(fout);
}
假设k等于5,成功打印出前5个最大的数据
文章来源:https://www.toymoban.com/news/detail-754375.html
文章来源地址https://www.toymoban.com/news/detail-754375.html
到了这里,关于【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!