【数据结构入门】-堆的实现以及堆排序（1）

2023-05-18 121

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构入门】-堆的实现以及堆排序（1）

堆的实现

接口函数

//初始化
void HeapInit(HP* php);
//插入数据
void HeapPush(HP* php,HPDataType x);
//删除数据
void HeapPop(HP* php);
//取堆顶数据
HPDataType HeapTop(HP* php);
//是否为空
bool HeapEmpty(HP* php);
//堆中元素的个数
int HeapSize(HP* php);

结构

typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;

初始化

//初始化
void HeapInit(HP* php)
{
  assert(php);
  php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);
  if (php->a = NULL)
  {
  perror("malloc fail\n");
  return;
  }
  php->size = 0;
  php->capacity = 4;
}

数据的插入

//插入数据
void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  //既然是插入数据，那么首先要检查是否需要扩容
  if (php->size == php->capacity)
  {
  HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
  if (tmp == NULL)
  {
    perror("realloc fail");
    return;
  }
  php->a = tmp;
  php->capacity *= 2;
  }
  php->a[php->size] = x;//size是最后一个数据的下一个数据的下标
  php->size++;
  AdjustUp(php->a, php->size - 1);
}

这里需要注意的是size是最后一个位置的下一个位置的下标。

当我们插入完数据后并没有完成我们的任务，我们还应该保证插入数据后此时依然符合堆的规则。

而这个规则就是向上调整，从插入数据的位置开始向上调整。

交换数据

//交换数据
void swap(HPDataType* p1, HPDataType* p2)
{
  HPDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

向上调整算法

//向上调整
void AdjustUp(HPDataType* a, int child)
{
  //父亲就是(孩子-1)/2
  int parent = (child - 1) / 2;
  while (child>0)
  {
  if (a[child] > a[parent])
  {
    swap(&a[child], &a[parent]);
    child = parent;
    parent = (child - 1) / 2;
  }
  else
  {
    break;
  }
  }
}

向上调整时需要注意我们的while循环条件，应该是child>0，而不是parent>=0，这是因为parent是永远>=0的，但是由于break的作用导致程序并不会死循环，最终会由break结束整个循环。

其实到这里我们的插入数据来进行堆的插入就已经算完成了。

删除数据

既然要删除数据的话，我们就应该知道我们应该删除哪里的数据，如果我们要删除尾的话，当然很好删除，但是如果仔细想一想的话删除尾的话好像没有什么意义；所以说这里我们要进行删除的是堆顶的数据，不仅仅是大根堆，小根堆也是会删除堆顶的数据。

那我们怎么删除堆顶的数据呢？首先挪动删除数据这个方法是不可以的，因为挪动数据的话效率会显得非常的低，而且父子兄弟的关系全都乱了。

//删除数据
void HeapPop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));//没有数据时就不要删除了
  swap(&php->a[0], &php->a[php->size - 1]);
  php->size--;
  AdjustDown(php->a, php->size, 0);
}

向下调整算法

//向下调整

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;
  }
  }
}

这里有一个问题，因为a[child] < a[child + 1]这个地方我们怕越界，所以我们在前面加上了child + 1 < n来确保右孩子存在。如果我们开辟空间的时候开成偶数倍的空间是不是就不用担心越界的问题了呢？答案是否定的，如果是这样的话就成了只关注越界问题而不关注数据是否为有效数据。如果说右孩子这里的值是一个随机值（当然这并不是我们堆中的有效数据），恰好这个随机值比我们的左孩子要大，此时由于child++，所以我们比较的就是右孩子和父亲之间的关系了，但问题是右孩子这里是一个随机值啊，并不是堆中的有效数据，然后程序运行下来就会造成一系列的问题。所以开辟成偶数倍的空间并不会解决问题。

堆是否为空

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

取堆顶数据

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

堆中有多少元素

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

测试

如果我们要取前k个数据，请看：

堆实现总代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
int main()
{
  HP hp;
  HeapInit(&hp);
  HeapPush(&hp, 4);
  HeapPush(&hp, 18);
  HeapPush(&hp, 42);
  HeapPush(&hp, 12);
  HeapPush(&hp, 2);
  HeapPush(&hp, 3);
  int i = 0;
  scanf("%d", &i);
  while (!HeapEmpty(&hp) && i--)
  {
  printf("%d ", HeapTop(&hp));
  HeapPop(&hp);
  }
  printf("\n");
  return 0;
}

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
//初始化
void HeapInit(HP* php)
{
  assert(php);
  php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);
  if (php->a == NULL)
  {
  perror("malloc fail\n");
  return;
  }
  php->size = 0;
  php->capacity = 4;
}
void swap(HPDataType* p1, HPDataType* p2)
{
  HPDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, int child)
{
  //父亲就是(孩子-1)/2
  int parent = (child - 1) / 2;
  while (child>0)
  {
  if (a[child] > a[parent])
  {
    swap(&a[child], &a[parent]);
    child = parent;
    parent = (child - 1) / 2;
  }
  else
  {
    break;
  }  
  }
}
//插入数据
void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  //既然是插入数据，那么首先要检查是否需要扩容
  if (php->size == php->capacity)
  {
  HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
  if (tmp == NULL)
  {
    perror("realloc fail");
    return;
  }
  php->a = tmp;
  php->capacity *= 2;
  }
  php->a[php->size] = x;//size是最后一个数据的下一个数据的下标
  php->size++;
  AdjustUp(php->a, php->size - 1);
}
//向下调整
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 HeapPop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));//没有数据时就不要删除了
  swap(&php->a[0], &php->a[php->size - 1]);
  php->size--;
  AdjustDown(php->a, php->size, 0);
}
HPDataType HeapTop(HP* php)
{
  assert(php);
  return php->a[0];
}
bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}
int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}
void HeapDestroy(HP* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->capacity = php->size = 0;
}

Heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;
//初始化
void HeapInit(HP* php);
//插入数据
void HeapPush(HP* php,HPDataType x);
//删除数据
void HeapPop(HP* php);
//取堆顶数据
HPDataType HeapTop(HP* php);
//是否为空
bool HeapEmpty(HP* php);
//堆中元素的个数
int HeapSize(HP* php);
void HeapDestroy(HP* php);
void HeapInitArray(HP* php, int* a, int n);
void AdjustDown2(int* a, int n, int parent);