【数据结构】堆的实现

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

1.堆的由来

普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。

2.堆的概念及结构

  • 大堆每一个父节点的值都大于等于子节点所对应的值而根节点的值就是最大的

  • 小堆每一个父节点的值都小于等于子节点所对应的值而根节点的值就是最小的

堆的性质

  • 堆中某个节点的值总是不大于或不小于其父节点的值；

  • 堆总是一棵完全二叉树。

3.堆的实现

首先打开VS在源文件选项建立test.c(用来测试)和Heap.c(用来写头文件里面的定义)的文件在头文件选项里建立Heap.h.

Heap.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//创建堆结构
typedef int HPDataType;//堆中存储数据的类型
typedef struct Heap
{
    int* a;//用于存储数据
    int size;//记录堆中的有效元素个数
    int capacity;//记录堆的容量
}HP;

3.1 初始化

Heap.h

void HeapInit(HP* hp);//初始化

Heap.c

#include "Heap.h"
void HeapInit(HP* hp)
{
    assert(hp);
    hp->a = NULL;
    hp->size = hp->capacity = 0;
}

3.2 销毁

Heap.h

void HeapDestory(HP* hp);//销毁

Heap.c

void HeapDestory(HP* hp)
{
    assert(hp);
    free(hp->a);
    hp->size = hp->capacity = 0;
}

3.3 打印

Heap.h

void HeapPrint(HP* hp);//打印

Heap.c

void HeapPrint(HP* hp)
{
    for (int i = 0; i < hp->size; i++)
    {
        printf("%d ", hp->a[i]);
    }
    printf("\n");
}

3.4 交换

Heap.h

void Swap(HPDataType* pa,HPDataType* pb);//交换

Heap.c

void Swap(HPDataType* pa, HPDataType* pb)
{
    HPDataType tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}

3.5 向上调整

调整过程

Heap.h

void AdjustUp(int* a, int child);//向上调整

Heap.c

void AdjustUp(int* a, int child)
{
    assert(a);
    int parent = (child - 1) / 2;
    while (child>0)
    {
        //if (a[child] > a[parent])//大堆
        if (a[child] < a[parent])//小堆
        {
            Swap(&a[child],&a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

3.6 插入

Heap.h

void HeapPush(HP* hp, HPDataType x);//插入

Heap.c

void HeapPush(HP* hp, HPDataType x)
{
    assert(hp);
    if (hp->size == hp->capacity)
    {
        size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
        HPDataType* tmp = 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, hp->size - 1);
}

test.c

#include "Heap.h"

int main()
{
    int a[] = { 70,56,30,25,15,10,75 };
    HP hp;
    HeapInit(&hp);
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        HeapPush(&hp, a[i]);
    }
    HeapPrint(&hp);
    return 0;
}

运行结果

3.7 向下调整

  • 找出左右孩子中最小的那个

  • 跟父亲比较如果比父亲小就交换

  • 再从交换的孩子位置继续往下调整

调整过程

Heap.h

void AdjustDown(int* a, int n, int parent);//向下调整

Heap.c

void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        //选出左右孩子中小的那个
        if (a[child + 1] < a[child] && child + 1 < n)
        {
            ++child;
        }
        //如果小的孩子小于父亲则交换并继续向下调整
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

3.8 判空

Heap.h

bool HeapEmpty(HP* hp);//判空

Heap.c

bool HeapEmpty(HP* hp)
{
    assert(hp);
    return hp->size == 0;
}

3.9 删除

Heap.h

void HeapPop(HP* hp);//删除

Heap.c

void HeapPop(HP* hp)
{
    assert(hp);
    assert(!HeapEmpty(hp));
    Swap(&hp->a[0], & hp->a[hp-> size - 1]);
    hp->size--;
    AdjustDown(hp->a, hp->size, 0);
}

test.c

#include "Heap.h"

int main()
{
    int a[] = { 70,56,30,25,15,10,75 };
    HP hp;
    HeapInit(&hp);
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        HeapPush(&hp, a[i]);
    }
    HeapPrint(&hp);
    HeapPop(&hp);
    HeapPrint(&hp);
    return 0;
}

运行结果

3.10 获取堆的元素个数

Heap.h

int HeapSize(HP* hp);//获取堆的元素个数

Heap.c

int HeapSize(HP* hp)
{
    assert(hp);
    return hp->size;
}

3.11 获取栈顶元素

Heap.h

HPDataType HeapTop(HP* hp);//获取堆顶元素

Heap.c

HPDataType HeapTop(HP* hp)
{
    assert(hp);
    assert(hp->size > 0);
    return hp->a[0];
}

4.完整代码展示

Heap.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//创建堆结构
typedef int HPDataType;//堆中存储数据的类型
typedef struct Heap
{
    int* a;//用于存储数据
    int size;//记录堆中的有效元素个数
    int capacity;//记录堆的容量
}HP;
void HeapInit(HP* hp);//初始化
void HeapDestory(HP* hp);//销毁
void HeapPrint(HP* hp);//打印
void HeapPush(HP* hp, HPDataType x);//插入
void HeapPop(HP* hp);//删除
void AdjustUp(int* a, int child);//向上调整
void Swap(HPDataType* pa,HPDataType* pb);//交换
void AdjustDown(int* a, int n, int parent);//向下调整
bool HeapEmpty(HP* hp);//判空
int HeapSize(HP* hp);//获取堆的元素个数
HPDataType HeapTop(HP* hp);//获取堆顶元素

Heap.c

#include "Heap.h"
void HeapInit(HP* hp)
{
    assert(hp);
    hp->a = NULL;
    hp->size = hp->capacity = 0;
}

void HeapDestory(HP* hp)
{
    assert(hp);
    free(hp->a);
    hp->size = hp->capacity = 0;
}

void HeapPrint(HP* hp)
{
    for (int i = 0; i < hp->size; i++)
    {
        printf("%d ", hp->a[i]);
    }
    printf("\n");
}

void AdjustUp(int* a, int child)
{
    assert(a);
    int parent = (child - 1) / 2;
    while (child>0)
    {
        if (a[child] < a[parent])
        {
            HPDataType tmp = a[child];
            a[child] = a[parent];
            a[parent] = tmp;
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

void HeapPush(HP* hp, HPDataType x)
{
    assert(hp);
    if (hp->size == hp->capacity)
    {
        size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
        HPDataType* tmp = 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 Swap(HPDataType* pa, HPDataType* pb)
{
    HPDataType tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}

void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        //选出左右孩子中小的那个
        if (a[child + 1] < a[child] && child + 1 < n)
        {
            ++child;
        }
        //如果小的孩子小于父亲则交换并继续向下调整
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

bool HeapEmpty(HP* hp)
{
    assert(hp);
    return hp->size == 0;
}


void HeapPop(HP* hp)
{
    assert(hp);
    assert(!HeapEmpty(hp));
    Swap(&hp->a[0], & hp->a[hp-> size - 1]);
    hp->size--;
    AdjustDown(hp->a, hp->size, 0);
}

int HeapSize(HP* hp)
{
    assert(hp);
    return hp->size;
}

HPDataType HeapTop(HP* hp)
{
    assert(hp);
    assert(hp->size > 0);
    return hp->a[0];
}

test.c

#include "Heap.h"

int main()
{
    int a[] = { 70,56,30,25,15,10,75 };
    HP hp;
    HeapInit(&hp);
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        HeapPush(&hp, a[i]);
    }
    HeapPrint(&hp);
    HeapPop(&hp);
    HeapPrint(&hp);
    return 0;
}
阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：「python｜语言特性」为什么f-string是python中最舒适的字符串格式化方式

下一篇：【黑马程序员】C++核心编程2 -类与对象（封装、继承和多态）-this指针-友元-运算重载符-文本操作（附测试用例源码、测试结果图及详细注释）

“【数据结构】堆的实现” 的相关文章

重写和重载的区别1年前 (2023-02-02)
中国电子学会2022年03月份青少年软件编程Scratch图形化等级考试试卷四级真题(含答案)1年前 (2023-02-02)
Web前端学习笔记2——表格1年前 (2023-02-02)
Jitpack发布Android库出现Direct local .aar file dependencies are not supported when building an AAR1年前 (2023-02-02)
CodeQL练习11年前 (2023-02-02)
Kali Linux利用MSF入侵安卓手机(小白版超详细)_kali入侵安卓手机1年前 (2023-02-02)
【Java 数据结构】实现一个二叉搜索树1年前 (2023-02-02)
linux 高效压缩工具之xz的压缩解压使用1年前 (2023-02-02)
12.ThreadLocal的那点小秘密1年前 (2023-02-02)
微信小程序开发 开启1年前 (2023-02-02)

阿里云国际版