一个小脑袋

一个小脑袋

关注
发信
关注(28)粉丝(399)

数据结构——堆的实现

目录：

一、堆的实现

1.1堆的定义

堆（heap）是特殊的数据结构。堆通常是一个可以被看做一棵完全二叉树(逻辑层面上)的数组对象(物理层面上),常用来在一组变化频繁(发生增删查改的频率较高)的数据中寻找最值.将根结点最大的堆叫做最大堆或大根堆，这样可以找到堆中的最大值(根节点的值);根结点最小的堆叫做最小堆或小根堆,这样可以找到堆中的最小值。

最大堆，最小堆如图：
数据结构——堆的实现-LMLPHP

1.2堆的实现

用数组实现一个堆

1.2.1堆的各个接口

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.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);
// 取堆顶的数据
HPDataTypeHeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

1.2.2堆的向上调整

//向上调整算法
void HeapJustUp(HPDataType a[], HPDataType child)
{
    int parsent;
    parsent = (child - 1) / 2;//找到孩子的父亲
    while (child > 0)
    {
        int tmp = 0;
        if (a[parsent] < a[child])//孩子比父亲的值大，
        {
            tmp = a[child];
            a[child] = a[parsent];
            a[parsent] = tmp;
        }
        else
            break;
        child = parsent;
        parsent = (parsent - 1) / 2;//找到孩子的父亲
    }
}

1.2.3堆的向下调整

void HeapJustDown(Heap* hp)
{
    //先假设当前待调整结点的左孩子结点存在
        //并且是待调整结点的左右孩子结点（不管右孩子结点存不存在，都这样假设）中值最大的
    int parent = 0;//根节点
    int child = parent * 2 + 1;//孩子结点
        while (child < hp->_size)
        {
            //child+1 < hp->_size说明右孩子结点确实存在
            //如果hp->_a[child] < hp->_a[child+1]也成立，那说明左右孩子结点中值最大的是右孩子结点
            if ((child + 1 < hp->_size) && hp->_a[child] < hp->_a[child + 1])
            {
                child = child + 1;
            }
            //如果a[child]>a[parent],则说明父节点比比左右孩子节点的值都要小，要置换
            if (hp->_a[child] > hp->_a[parent])
            {
                int tmp = hp->_a[parent];
                hp->_a[parent] = hp->_a[child];
                hp->_a[child] = tmp;
                parent = child;
                child = child * 2 + 1;
            }
            //如果a[child] <= a[parent],那就不需要进行调整
            else
            {
                break;
            }
        }
}

1.2.4堆的定义声明和初始化

1.堆的声明

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;//动态数组
	int _size;//存储数据的下标
	int _capacity;//动态数组的容量
}Heap;

2.堆的初始化

// 堆的初始化
void HeapInit(Heap* hp)
{
    hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
    if (hp->_a == 0)
    {
        printf("malloc is error\n");
        exit(-1);
    }
    hp->_capacity = 4;
    hp->_size = 0;
}

1.2.5堆的数据处理

1.堆的插入

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
    //数据满了，需要扩容
    if (hp->_capacity == hp->_size)
    {
        HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType)*hp->_capacity * 2);
        if (tmp == NULL)
        {
            printf("realloc is error");
            exit(-1);
        }
        hp->_a = tmp;
        hp->_capacity = hp->_capacity * 2;
    }
    //不需要扩容
    hp->_a[hp->_size++] = x;//插入数据，然后_size+1
    //一般数据都是放到数组尾得，建堆，向上调整，这里我们建大堆
    HeapJustUp(hp->_a, hp->_size - 1);
}

2.堆的删除

// 堆的删除，从堆顶开始删
void HeapPop(Heap* hp)
{
assert(hp);//断言为空为假的话就报错
assert(!HeapEmpty(hp));//断言如果不是空为真就执行
//首元素的的值与尾元素交换，然后删除尾元素
int tmp = hp->_a[0];
hp->_a[0] = hp->_a[hp->_size - 1];
hp->_a[hp->_size - 1] = tmp;
hp->_size--;
//堆顶元素进行向下调整
HeapJustDown(hp);
}

3.获取堆顶数据

// 取堆顶的数据
HPDataTypeHeapTop(Heap* hp)
{
    assert(hp->_a);
    assert(!HeapEmpty(hp));//断言如果不是空为真就执行
    return hp->_a[0];
}

1.2.6堆的判空和堆的数据个数以及堆销毁

1.堆的数据个数

// 堆的数据个数
int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->_size;
}

2.堆的判空

// 堆的判空
int HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->_size == 0;
}

3.堆销毁

// 堆的销毁
void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->_a);
    hp->_a = NULL;
    hp->_capacity = hp->_size = 0;
}

1.2.7堆的代码实现

.h头文件（声明）

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.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);
// 取堆顶的数据
HPDataTypeHeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

.c源文件（定义）

#include "Heap.h"
// 堆的构建
void HeapInit(Heap* hp)
{
    hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
    if (hp->_a == 0)
    {
        printf("malloc is error\n");
        exit(-1);
    }
    hp->_capacity = 4;
    hp->_size = 0;
}
//向上调整算法
HeapJustUp(HPDataType a[], HPDataType child)
{
    int parsent;
    parsent = (child - 1) / 2;//找到孩子的父亲
    while (child > 0)
    {
        int tmp = 0;
        if (a[parsent] < a[child])//孩子比父亲的值大，
        {
            tmp = a[child];
            a[child] = a[parsent];
            a[parsent] = tmp;
        }
        else
            break;
        child = parsent;
        parsent = (parsent - 1) / 2;//找到孩子的父亲
    }
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
    //数据满了，需要扩容
    if (hp->_capacity == hp->_size)
    {
        HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType)*hp->_capacity * 2);
        if (tmp == NULL)
        {
            printf("realloc is error");
            exit(-1);
        }
        hp->_a = tmp;
        hp->_capacity = hp->_capacity * 2;
    }
    //不需要扩容
    hp->_a[hp->_size++] = x;//插入数据，然后_size+1
    //一般数据都是放到数组尾得，建堆，向上调整，这里我们建大堆
    HeapJustUp(hp->_a, hp->_size - 1);
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->_size == 0;
}
//堆顶元素进行向下调整
void HeapJustDown(Heap* hp)
{
    //先假设当前待调整结点的左孩子结点存在
        //并且是待调整结点的左右孩子结点（不管右孩子结点存不存在，都这样假设）中值最大的
    int parent = 0;//根节点
    int child = parent * 2 + 1;//孩子结点
        while (child < hp->_size)
        {
            //child+1 < hp->_size说明右孩子结点确实存在
            //如果hp->_a[child] < hp->_a[child+1]也成立，那说明左右孩子结点中值最大的是右孩子结点
            if ((child + 1 < hp->_size) && hp->_a[child] < hp->_a[child + 1])
            {
                child = child + 1;
            }
            //如果a[child]>a[parent],则说明父节点比比左右孩子节点的值都要小，要置换
            if (hp->_a[child] > hp->_a[parent])
            {
                int tmp = hp->_a[parent];
                hp->_a[parent] = hp->_a[child];
                hp->_a[child] = tmp;
                parent = child;
                child = child * 2 + 1;
            }
            //如果a[child] <= a[parent],那就不需要进行调整
            else
            {
                break;
            }
        }
}
// 堆的删除，从堆顶开始删
void HeapPop(Heap* hp)
{
assert(hp);//断言为空为假的话就报错
assert(!HeapEmpty(hp));//断言如果不是空为真就执行
//首元素的的值与尾元素交换，然后删除尾元素
int tmp = hp->_a[0];
hp->_a[0] = hp->_a[hp->_size - 1];
hp->_a[hp->_size - 1] = tmp;
hp->_size--;
//堆顶元素进行向下调整
HeapJustDown(hp);
}
// 取堆顶的数据
HPDataTypeHeapTop(Heap* hp)
{
    assert(hp->_a);
    assert(!HeapEmpty(hp));//断言如果不是空为真就执行
    return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->_size;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->_a);
    hp->_a = NULL;
    hp->_capacity = hp->_size = 0;
}

.c源文件（测试）

#include "Heap.h"
int main()
{
    Heap hp;
    HeapInit(&hp);//初始化
    HeapPush(&hp, 2);//插入数据
    HeapPush(&hp, 3);
    HeapPush(&hp, 4);
    HeapPush(&hp, 5);
    HeapPush(&hp, 6);
    HeapPush(&hp, 1);
    HeapPush(&hp, 66);
    HeapPush(&hp, 62);
    HeapPush(&hp, 4);
    HeapPush(&hp, 6);
    HeapPop(&hp);//删除数据,从堆顶开始删
   int tmp= HPDataTypeHeapTop(&hp);//取堆顶元素
    // 堆的数据个数
   int num = HeapSize(&hp);
   printf("建大堆，栈顶元素为：%d,堆的数据个数：%d\n", tmp,num);
    for (int i = 0; i < num; i++)
        printf("%d ", hp._a[i]);
    HeapDestory(&hp);// 堆的销毁
    return 0;
}

二、TOP—K问题

TOP—K问题：求数据集合中前k个最大的元素和最小的元素，一般情况数据非常大。
如：专业前10，世界500强，游戏中前100的活跃玩家，各种榜单等等。

例子：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define n 100000000
void  WeinteData()//写入1亿数据
{
    
FILE* fp = fopen("top.txt", "w");//打开文件，只写
if (fp == NULL)
{
    perror("fopen error");
    exit(-1);
}
srand((unsigned)time(0));
int arr[100] = { 0 };
for (int i = 0; i < n; i++)
{
    int x = rand() % 10000 + 1;
    fprintf(fp, "%d\n", x);
}
fclose(fp);//关闭文件
}
//两个数交换
void Swap(int* p, int* q)
{
    int tmp;
    tmp = *q;
    *q = *p;
    *p = tmp;
}
//向下调整算法
void JustDown(int* arr,int k,int parent)
{
    int child = parent * 2 + 1;//左孩子结点
    while (child < k)
    {
        if ((child + 1 < k) && arr[child] > arr[child + 1])//找到最小值的孩子结点
            child += 1;
        //如果arr[child]<arr[parent],则说明父节点比比左右孩子节点的值都要大，要置换
        if (arr[child] < arr[parent])
        {
            Swap(&arr[child], &arr[parent]);
           //让孩子结点为父节点，并且更新它的儿子结点
            parent = child;
            child = child * 2 + 1;
        }
        //如果a[child] <= a[parent],那就不需要进行调整
        else
        {
            break;
        }
    }
}
//建小堆
void HeapCreate(int* arr,int k)
{
    //最后一个结点的父亲结点开始向下调整
    for (int i = (k - 2) / 2; i >= 0; --i)
    {
        //向下调整算法
        JustDown(arr, k, i);
    }
}
void  FileTakeK()
{
    int k = 10;//10个数
    int* a = (int*)malloc(sizeof(int) * k);//开辟一块空间用来建堆
    if (a == NULL)
    {
        perror("malloc error:");
        exit(-1);
    }
    FILE* file = fopen("top.txt", "r");//打开top.txt文件,只读模式
    if (file == NULL)
    {
        perror("fopen error:");
        exit(-1);
    }
    for (int i = 0; i < k; i++)
    {
        fscanf(file, "%d", &a[i]);
    }
    printf("前10个数:\n");
    for (int i = 0; i < k; i++)
        printf("%d ", a[i]);
    //建小堆
    HeapCreate(a, k);
    printf("\n建完小堆里面的数:\n");
    for (int i = 0; i < k; i++)
        printf("%d ", a[i]);
    //把剩余的n-k个数与小堆的堆顶比较，比较完成后，堆里的数就是文件里最大的10个数
    int x = 0;
    while (fscanf(file, "%d", &x) != EOF)
    {
        //比堆顶数大，把这个数赋值给堆顶，然后向下调整
        if (x > a[0])
            a[0] = x;
        JustDown(a, k, 0);
    }
    printf("\n取最大的10个数:\n");
    for (int i = 0; i < k; i++)
        printf("%d ", a[i]);
    free(a);//释放内存
    fclose(file);//关闭文件
}
int main()
{
    //写入1亿数据
   WeinteData();
       //从文件中取出k个数,建小堆
    FileTakeK();
    return 0;
}
11-25 07:37
Powered by LMLPHP ©2024 一个小脑袋 0.002000