堆 (带图详解)

2022-12-01 18:01:12 浏览数 (1)

开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第3天，点击查看活动详情 @TOC

1.堆的基本概念

1. 概念

如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

2.性质

1.必须为完全二叉树

2.满足大堆/小堆成立的条件

  • 大堆：树中所有父亲节点都大于等于孩子节点
  • 小堆：树中所有父亲节点都小于等于孩子节点

3.存储方式

1.逻辑结构

  • 逻辑结构：我们想象出来的

2.物理结构

  • 物理结构：实实在在在内存是如何存储的

4. 孩子与父亲之间下标的关系

  • leftchild=parent*2 1
  • rightchild=parent*2 2
  • parent=(child-1)/2

这里child 可以是leftchild，也可以是rightchild，因为整数相除得到的结果也为整数

2.堆的基本实现

1.push——插入

1.代码

代码语言：javascript复制
void adjustup(HPDatatype* a, int child)//向上调整算法
{
    int parent = (child - 1) / 2;
        while (child>0)
    {
        if (a[parent] >a[child])//以小堆为例
        {
        swap(&amp;a[parent], &amp;a[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
     }
}
void heappush(HP* php, HPDatatype x)//插入
{
    assert(php);
    if (php->capacity == php->size)//扩容
    {
        HPDatatype* ptr = (HPDatatype*)realloc(php->a, sizeof(HPDatatype)*php->capacity * 2);
        if (ptr != NULL)
        {
            php->a = ptr;
            php->capacity *= 2;
        }
    }
    php->a[php->size  ] = x;//插入数据
    adjustup(php->a,php->size-1);  //向上调整

}

2. 情况分析

由图可知目前是一个小堆

情况1
  • 在数组后插入 >=56 的数 例如 100

此时依旧为一个小堆，不需要调整，直接插入在数组尾部就可以了

情况2
  • 在数组后插入<56的数 例如 22
  • 在圈中22比56小，所以不构成小堆，需要进行向上调整

3. 向上调整算法

1.过程分析
  • 这里以小堆为例
  • 我们要创建小堆，parent(56)>child(22)，所以要将两者值进行交换
  • 假设我们并不知道上面的数 例如10 与 新交换后的parent 22 的关系 所以我们需要向上调整
  • 即将 parent的下标赋给 child ，即22成为新的child下标对应位置，10成为parent下标对应位置 ，此时因为10<22，所以走break不需要调整
2. 临界条件的判断
  • 当child下标处于0时，parent下标已经越界没有比较的必要了，所以child>0 就为临界条件

2. pop—— 删除

1.代码

代码语言：javascript复制
void adjustdown(HPDatatype* a, int parent,int size)//向下调整算法
{
    int child = parent * 2   1;//假设为左孩子
    while (child<size)
    {
        if (child 1<size&amp;&amp;a[child] < a[child   1])//如果假设不成立，就为右孩子
        {
            child  ;
        }
        if (a[parent] < a[child])//孩子大于父亲
        {
            swap(&amp;a[parent], &amp;a[child]);
            parent = child;
            child=parent * 2   1;
        }
        else
        {
            break;
        }
    }
}
void heappop(HP* php)//删除
{
    assert(php);
    assert(php->size > 0);
    swap(&amp;php->a[0], &amp;php->a[php->size - 1]);
    php->size--;
    adjustdown(php->a,0,php->size);//向下调整算法
}

2. 向下调整算法

1. 注意事项

若右孩子所对应没有结点，a[child 1]就会越界访问， 所以需要加上限制条件： child 1<size

2. 临界条件
  • child作为下标存在，n为数据个数，child最多等于n-1
3.TOPK问题
  • N个数，找最大/最小的前k个

这里我们以大堆来举例 寻找最大的前k个

1.过程分析
  • 刚开始时，我们需要将首尾互换，并将此时的尾数据删除
  • 交换parent下标与child下标所对应的值，如图1 2
  • 并将child的下标赋给parent 如 图 2 3

3. create ——建堆

代码语言：javascript复制
void heapcreate(HP* php, HPDatatype* a, int n)//建堆
{
    assert(php);
    php->a = (HPDatatype*)malloc(sizeof(HPDatatype) * n);
    if (php->a == NULL)
    {
        perror("mealloc fail");
        exit(-1);
    }
    memcpy(php->a, a,  sizeof(HPDatatype) * n);
    int i = 0;
    for (i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        adjustdown(php->a, i, n);
    }

}

1.向下调整算法的应用

我们想创建一个大堆，就必须使左子树是一个大堆及右子树是一个大堆 所以要从倒数第二层开始调整

4. top—— 取堆顶元素

代码语言：javascript复制
HPDatatype heaptop(HP* php)
{
    assert(php);
    assert(php->size > 0);
    return php->a[0];
}

5. size—— 数据个数

代码语言：javascript复制
int heapsize(HP* php)//数据个数
{
    assert(php);
    assert(php->size > 0);
    return php->size;
}

6. empty ——判空

代码语言：javascript复制
bool heapempty(HP* php)//判断是否为空
{
    assert(php);
    assert(php->size > 0);
    return php->size == 0;
}

7. TOPK问题的具体实现

代码语言：javascript复制
#include "heap.h"
int main()
{
    HP php;
    heapinit(&amp;php);
    int arr[] = {27,15,19,18,28,34,65,49,25,37};
    int sz = sizeof(arr) / sizeof(arr[0]);
    int i = 0;
    for (i = 0; i < sz; i  )
    {
        heappush(&amp;php, arr[i]);
    }
    print(&amp;php);
    int k = 5;//取前5个数
    while (k--)
    {
        printf("%d ", heaptop(&amp;php));
        heappop(&amp;php);
    }
    heapdestroy(&amp;php);
    return 0;
}

完整代码

1.heap.h

代码语言：javascript复制
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int  HPDatatype;
typedef struct Heap
{
    HPDatatype* a;
    int size;
    int capacity;
}HP;
void heapcreate(HP* php, HPDatatype *a, int size);
void heapinit(HP* php);//初始化
void heapdestroy(HP* php);//内存销毁
void heappush(HP* php,HPDatatype x);//插入
void heappop(HP* php);//删除
HPDatatype heaptop(HP* php);//堆顶数据
int heapsize(HP* php);//数据个数
bool heapempty(HP* php);//判断是否为空

2.heap.c

代码语言：javascript复制
#include"heap.h"
void heapcreate(HP* php, HPDatatype *a, int n)//建堆
{
    assert(php);
    php->a = (HPDatatype*)malloc(sizeof(HPDatatype) * n);
    if (php->a == NULL)
    {
        perror("mealloc fail");
        exit(-1);
    }
    memcpy(php->a, a,  sizeof(HPDatatype) * n);
    php->size = n;
    php->capacity = n;
    int i = 0;
    for (i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        adjustdown(php->a, i, n);
    }

}



void  heapinit(HP* php)//初始化
{
    assert(php);
    php->a = (HP*)malloc(sizeof(php) *4);
    php->size = 0;
    php->capacity = 4;
}

void heapdestroy(HP* php)//内存销毁
{
    assert(php);
    free(php->a);
    php->a = NULL;
    php->size = 0;
    php->capacity = 0;
}
void swap(HPDatatype* s1, HPDatatype* s2)
{
    int tmp = 0;
    tmp = *s1;
    *s1 = *s2;
    *s2 = tmp;
}
//void adjustup(HPDatatype* a, int child)//向上调整算法
//{
//	int parent = (child - 1) / 2;
//	while (child>0)
//	{
//		if (a[parent] >a[child])//以小堆为例
//		{
//			swap(&amp;a[parent], &amp;a[child]);
//			child = parent;
//			parent = (child - 1) / 2;
//	    }
//		else
//		{
//			break;
//		}
//	}
//}
void adjustup(HPDatatype* a, int child)//向上调整算法
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[parent] < a[child])//以大堆为例
        {
            swap(&amp;a[parent], &amp;a[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

void heappush(HP* php, HPDatatype x)//插入
{
    assert(php);
    if (php->capacity == php->size)//扩容
    {
        HPDatatype* ptr = (HPDatatype*)realloc(php->a, sizeof(HPDatatype)*php->capacity * 2);
        if (ptr != NULL)
        {
            php->a = ptr;
            php->capacity *= 2;
        }
    }
    php->a[php->size  ] = x;//插入数据
    adjustup(php->a,php->size-1);  //向上调整

}
void adjustdown(HPDatatype* a, int parent,int size)//向下调整算法
{
    int child = parent * 2   1;//假设为左孩子
    while (child<size)
    {
        if (child 1<size&amp;&amp;a[child] < a[child   1])//如果假设不成立，就为右孩子
        {
            child  ;
        }
        if (a[parent] < a[child])//孩子大于父亲
        {
            swap(&amp;a[parent], &amp;a[child]);
            parent = child;
            child=parent * 2   1;
        }
        else
        {
            break;
        }
    }
}
void heappop(HP* php)//删除
{
    assert(php);
    assert(php->size > 0);
    swap(&amp;php->a[0], &amp;php->a[php->size - 1]);
    php->size--;
    adjustdown(php->a,0,php->size);//向下调整算法
}
HPDatatype heaptop(HP* php)//取堆顶元素
{
    assert(php);
    assert(php->size > 0);
    return php->a[0];
}

void print(HP* php)
{
    int i = 0;
    for (i = 0; i < php->size; i  )
    {
        printf("%d ", php->a[i]);
    }
    printf("n");
}
bool heapempty(HP* php)//判断是否为空
{
    assert(php);
    assert(php->size > 0);
    return php->size == 0;
}

int heapsize(HP* php)//数据个数
{
    assert(php);
    assert(php->size > 0);
    return php->size;
}
代码语言：javascript复制
#include "heap.h"
int main()
{
    HP php;
    heapinit(&amp;php);
    int arr[] = {27,15,19,18,28,34,65,49,25,37};
    int sz = sizeof(arr) / sizeof(arr[0]);
    int i = 0;
    for (i = 0; i < sz; i  )
    {
        heappush(&amp;php, arr[i]);
    }
    print(&amp;php);
    int k = 5;
    while (k--)
    {
        printf("%d ", heaptop(&amp;php));
        heappop(&amp;php);
    }
    heapdestroy(&amp;php);
    return 0;
}

3.test.c

代码语言：javascript复制
#include "heap.h"
int main()
{
    HP php;
    int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    int i = 0;
    heapcreate(&amp;php, arr, sz);
    print(&amp;php);
    /*for (i = 0; i < sz; i  )
    {
        heappush(&amp;php, arr[i]);
    }
    print(&amp;php);*/
    int k = 5;
    while (k--)
    {
        printf("%d ", heaptop(&amp;php));
        heappop(&amp;php);
    }
    heapdestroy(&amp;php);
    return 0;
}
编程算法 存储 二叉树

0 人点赞