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

堆的实现（完全注释版本）

article 2024/11/27 11:48:27

头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
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);

函数实现

#define _CRT_SECURE_NO_WARNINGS 1
#include "t.h"
// 堆的初始化
void HeapInit(Heap* hp) {
    assert(hp);         // 确保堆指针不为空
    hp->a = NULL;       // 动态数组初始化为空
    hp->size = 0;       // 当前堆的大小初始化为0
    hp->capacity = 0;   // 当前堆的容量初始化为0
}
// 堆的销毁
void HeapDestory(Heap* hp) {
    assert(hp);         // 确保堆指针不为空
    free(hp->a);        // 释放动态数组的内存
    hp->a = NULL;       // 将指针置空，防止野指针
    hp->size = 0;       // 将大小重置为0
    hp->capacity = 0;   // 将容量重置为0
}
// 交换两个堆元素的值
void swap(HPDataType* px, HPDataType* py) {
	HPDataType newdata = *px;
	*px = *py;
	*py = newdata;
}
// 向上调整堆
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 AdjustDown(HPDataType* a, int n, int parent) {
    int child = parent * 2 + 1;  // 找到左孩子的索引
    while (child < n) {          // 当孩子节点在有效范围内
        // 找到较大的孩子节点
        if (child + 1 < n && a[child] < a[child + 1]) {
            ++child; // 更新为右孩子的索引
        }
        // 如果孩子大于父节点，交换并继续向下调整
        if (a[child] > a[parent]) {
            swap(&a[child], &a[parent]);
            parent = child;          // 更新父节点为孩子节点
            child = parent * 2 + 1;  // 更新左孩子索引
        } else {
            break; // 如果满足堆性质，停止调整
        }
    }
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x) {
    assert(hp);  // 确保堆指针不为空
    // 如果堆已满，则扩容
    if (hp->size == hp->capacity) {
        int newcapaity = hp->capacity == 0 ? 4 : hp->capacity * 2; // 扩容为当前容量的两倍
        HPDataType* tmp = (HPDataType*) realloc(hp->a, sizeof(HPDataType) * newcapaity);
        if (tmp == NULL) {  // 如果分配失败
            perror("realloc fail");
            return;
        }
        hp->a = tmp;           // 更新堆数组指针
        hp->capacity = newcapaity; // 更新堆容量
    }
    // 将新元素插入到堆尾，并向上调整
    hp->a[hp->size] = x;
    hp->size++;
    AdjustUp(hp->a, hp->size - 1);
}
// 堆的删除
void HeapPop(Heap* hp) {
    assert(hp);           // 确保堆指针不为空
    assert(hp->size > 0); // 确保堆不为空
    // 交换堆顶和堆尾元素
    swap(&hp->a[0], &hp->a[hp->size - 1]);
    hp->size--;           // 减少堆的大小
    AdjustDown(hp->a, hp->size, 0); // 调整堆顶元素以恢复堆性质
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp) {
	assert(hp);// 确保堆指针不为空
	return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp){
	assert(hp);// 确保堆指针不为空
	return hp->size;
}
// 堆的判空
bool HeapEmpty(Heap* hp) {
	assert(hp);	// 确保堆指针不为空
	return hp->size == 0;
}

测试文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"t.h"
int main(){
	int a[] = { 60,70,65,50,32,100 };
	Heap hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++){
		HeapPush(&hp, a[i]);
	}
	while (!HeapEmpty(&hp)){
		printf("%d\n", HeapTop(&hp));
		HeapPop(&hp);
	}
	HeapDestory(&hp);
	return 0;
}

实现效果