【数据结构】堆-阿里云开发者社区

堆的结构与实现

由于完全二叉树更适合使用顺序结构存储，现实中通常把堆（一种特殊二叉树）使用顺序结构的数组来存储。

堆的概念

如果由一个关键码的集合K={k₀,k₁,k₂,…,k_n-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：K_i<=K_2*i+1且K_i<=K_2*i+2(K_i>=K_2*i+1且K_i>=K_2*i+2)i=0,1,2…,则称为小堆（或者大堆）。

根据结点最大的堆叫做最大堆或者大根堆，根结点最小的堆叫做最小堆或者小根堆

堆的性质

堆中某个结点的值总是不大于或不小于其父结点的值
堆总是一棵完全二叉树

堆的实现

堆的初始化

堆由数组实现比较方便，size为数组的长度，capacity为数组的容量

typedef int HPDataType;
typedef struct Heap
{
  HPDataType* data;
  int size;
  int capacity;
}Heap;

//堆的创建（初始化）
void HeapInit(Heap* hp)
{
  hp->data = (HPDataType*)malloc(sizeof(HPDataType) * 5);
  if (hp->data == NULL)
  {
    perror("malloc fail");
    return;
  }
  hp->capacity = 5;
  hp->size = 0;
}

堆的调整

堆的向上调整

堆在向上向上调整时，child会与parent比较，以大根堆为例：如果child比parent大，则交换，否则停止。

//堆的向上调整
void HeapAdjustup(HPDataType* a, int child)
{
  while (child > 0)
  {
    int parent = (child - 1) / 2;
    if (a[child] cmp a[parent])
    {
      HPDataType tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp;
      child = parent;
    }
    else
    {
      break;
    }
  }
}

堆的向下调整

堆在向下调整时，考虑的情况要多一些，以大根堆为例：parent与俩个child比较，如果俩个child中较大值比parent大，则交换。在交换时，有个条件需要注意，即child可能比最后一个结点大，chlid的兄弟结点可能比最后一个结点大

//堆的向下调整
void HeapAdjustdown(HPDataType* a, int n, HPDataType parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    if (child + 1 < n && a[child + 1] cmp a[child])
    {
      child = child + 1;
    }
    if (a[child] cmp a[parent])
    {
      HPDataType tmp = a[parent];
      a[parent] = a[child];
      a[child] = tmp;
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

堆的创建

一个数组，逻辑上来讲是一棵完全二叉树，但是不复合堆的性质，可以通过算法来将数组调整为一个堆。

一般来讲，堆在创建的时候有俩种做法：向上调整建堆与向下调整建堆。

下面均以大根堆为例简绍：

向上调整建堆

向上调整建堆，即利用堆的向上调整，将数组逐渐扩大，扩大一个元素，向上调整一次。

#include<stdio.h>
void HeapAdjustup(int* arr, int child)
{
  while (child > 0)
  {
    int parent = (child - 1) / 2;
    if (arr[parent] < arr[child])
    {
      int tmp = arr[parent];
      arr[parent] = arr[child];
      arr[child] = tmp;
      child = parent;
    }
    else
    {
      break;
    }
  }
}
int main(void)
{
  int arr[] = { 3,4,5,15,6,19,24,14 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  //向上建堆
  int i = 0;
  for (i = 1; i < sz ; i++)
  {
    HeapAdjustup(arr,i);
  }
  //打印数组
  for (i = 0; i < sz ; i++)
  {
    printf("%d ",arr[i]);
  }
  printf("\n");
  return 0;
}

向下调整建堆

数组向下调整建堆时有一个条件：左右子树必须为推才可调整。

在向下调整建堆时，从最后一个叶子结点的父结点开始进行调整

从最后一个叶子结点的父结点开始向前逐个调整，即可满足条件

#include<stdio.h>
void HeapAdjustdown(int* arr, int parent,int n)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    if ((child + 1 < n) && (arr[child + 1] > arr[child]))
    {
      child++;
    }
    if (arr[child] > arr[parent])
    {
      int tmp = arr[child];
      arr[child] = arr[parent];
      arr[parent] = tmp;
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
int main(void)
{
  int arr[] = { 1,3,5,9,13,19,24,4,12,11 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  //堆的向下调整
  int i = 0;
  for (i = (sz - 1 - 1) / 2; i >= 0; i--)
  {
    HeapAdjustdown(arr,i,sz);
  }
  //打印
  for (i = 0; i < sz; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
  return 0;
}

建堆的时间复杂度

树的高度为h，T(N)表示建堆的总次数。

总结：

向下调整建堆的时间复杂度为：O(N)

向上调整建堆的时间复杂度为：O(N*logN)

堆的插入

堆在插入时，会插入到最后一个，然后进行向上调整

//堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
  assert(hp);
  if (hp->size == hp->capacity)
  {
    HPDataType* tmp = (HPDataType*)realloc(hp->data,sizeof(HPDataType) * hp->capacity * 2);
    if (tmp == NULL)
    {
      printf("realloc fail");
      return;
    }
    hp->data = tmp;
    hp->capacity *= 2;
  }
  hp->data[hp->size] = x;
  hp->size++;
  //堆的调整
  HeapAdjustup(hp->data,hp->size-1);
}

堆的删除

堆在删除的时候，会将顶部结点删除，过程为将顶部结点与尾部结点交换，size减1，然后进行向下调整。

//堆的删除
void HeapPop(Heap* hp)
{
  assert(hp);
  assert(!HeapEmpty(hp));
  
  HPDataType tmp = hp->data[0];
  hp->data[0] = hp->data[hp->size - 1];
  hp->data[hp->size - 1] = tmp;
  hp->size--;
  //向下调整
  HeapAdjustdown(hp->data, hp->size, 0);
}

堆的整体代码实现

heap.h

#pragma once
#define  _CRT_SECURE_NO_WARNINGS 1  
#define cmp >
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* data;
  int size;
  int capacity;
}Heap;
//堆的创建（初始化）
void HeapInit(Heap* hp);
//堆的销毁
void HeapDestory(Heap* hp);
//堆的插入
void HeapPush(Heap* hp, HPDataType x);
//堆的判空
bool HeapEmpty(Heap* hp);
//堆的向上调整
void HeapAdjustup(HPDataType* a, int child);
//堆的删除
void HeapPop(Heap* hp);
//堆的向下调整
void HeapAdjustdown(HPDataType* a, int n, HPDataType parent);
//堆顶数据
HPDataType HeapTop(Heap* hp);
//堆的数据个数
int HeapSize(Heap* hp);

heap.c

#include"heap.h"
//堆的创建（初始化）
void HeapInit(Heap* hp)
{
  assert(hp);
  hp->data = (HPDataType*)malloc(sizeof(HPDataType) * 5);
  if (hp->data == NULL)
  {
    perror("malloc fail");
    return;
  }
  hp->capacity = 5;
  hp->size = 0;
}
//堆的销毁
void HeapDestory(Heap* hp)
{
  assert(hp);
  assert(hp->data);
  free(hp->data);
  hp->data = NULL;
  hp->capacity = 0;
  hp->size = 0;
}
//堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
  assert(hp);
  if (hp->size == hp->capacity)
  {
    HPDataType* tmp = (HPDataType*)realloc(hp->data,sizeof(HPDataType) * hp->capacity * 2);
    if (tmp == NULL)
    {
      printf("realloc fail");
      return;
    }
    hp->data = tmp;
    hp->capacity *= 2;
  }
  hp->data[hp->size] = x;
  hp->size++;
  //堆的调整
  HeapAdjustup(hp->data,hp->size-1);
}
//堆的判空
bool HeapEmpty(Heap* hp)
{
  assert(hp);
  return hp->size == 0;
}
//堆的向上调整
void HeapAdjustup(HPDataType* a, int child)
{
  while (child > 0)
  {
    int parent = (child - 1) / 2;
    if (a[child] cmp a[parent])
    {
      HPDataType tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp;
      child = parent;
    }
    else
    {
      break;
    }
  }
}
//堆的删除
void HeapPop(Heap* hp)
{
  assert(hp);
  assert(!HeapEmpty(hp));
  
  HPDataType tmp = hp->data[0];
  hp->data[0] = hp->data[hp->size - 1];
  hp->data[hp->size - 1] = tmp;
  hp->size--;
  //向下调整
  HeapAdjustdown(hp->data, hp->size, 0);
}
//堆的向下调整
void HeapAdjustdown(HPDataType* a, int n, HPDataType parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    if (child + 1 < n && a[child + 1] cmp a[child])
    {
      child = child + 1;
    }
    if (a[child] cmp a[parent])
    {
      HPDataType tmp = a[parent];
      a[parent] = a[child];
      a[child] = tmp;
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
//堆顶数据
HPDataType HeapTop(Heap* hp)
{
  assert(hp);
  assert(!HeapEmpty(hp));
  return hp->data[0];
}
//堆的数据个数
int HeapSize(Heap* hp)
{
  assert(hp);
  return hp->size;
}

堆的应用

堆排序

堆排序，即利用堆的思想对数组进行排序。

步骤：

1.建堆

升序：建大堆
降序：建小堆

2.利用堆的思想实现排序

以升序建大堆为例：先将数组进行调整，将数组调整为堆的形式，利用堆删除的原理，将最大值与最后一个元素进行调整，然后进行向下调整，循环往复

实现排序：

#include<stdio.h>
void HeapAdjustdown(int* arr, int parent, int n)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    if ((child + 1 < n) && (arr[child + 1] > arr[child]))
    {
      child++;
    }
    if (arr[child] > arr[parent])
    {
      int tmp = arr[child];
      arr[child] = arr[parent];
      arr[parent] = tmp;
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
int main(void)
{
  int arr[] = { 3,5,7,8,12,16,11,15,1,2,6,19 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  //向下调整建堆——建大堆
  int i = 0;
  for (i = (sz - 1 - 1) / 2; i >= 0; i--)
  {
    HeapAdjustdown(arr, i, sz);
  }
  //排序——排升序
  int end = sz - 1;
  while (end>0)
  {
    int tmp = arr[end];
    arr[end] = arr[0];
    arr[0] = tmp;
    HeapAdjustdown(arr, 0, end);
    end--;
  }
  //打印
  for (i = 0; i < sz; i++)
  {
    printf("%d ", arr[i]);
  }
  return 0;
}

TOP-K问题

TOP-K问题：即求得数据结合中前K个最大的元素或者最小的元素，一般情况数据量都较大。

步骤：

1.用数据结合中前K个元素建堆

前K个最大的元素，建小堆
前K个最小的元素，建大堆

2.使用剩下的前N-K个元素依次与堆顶元素来比较，不满足则体替代元素

即在一个较大的数组中，找到里面最大的K个值，然后使用小堆，遍历较大数组中的数据，如果这个数组比小堆堆顶的数据还大，就代替其进堆，并使用向下调整，则最后这个小堆就是最大的前K个。

实现过程：

//TOP-K问题
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void HeapAdjustdown(int* arr, int parent, int n)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    if ((child + 1 < n) && (arr[child + 1] < arr[child]))
    {
      child++;
    }
    if (arr[child] < arr[parent])
    {
      int tmp = arr[child];
      arr[child] = arr[parent];
      arr[parent] = tmp;
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
//设置随机值
void Heaprand(int* arr)
{
  int i = 0;
  for (i = 0; i < 1000; i++)
  {
    arr[i] = rand() % 1000;
  }
}
//TOP
int main(void)
{
  //调用随机值
  srand((unsigned int)time(NULL));
  int arr[1000] = { 0 };
  Heaprand(arr);
  //利用TOP-K问题求最大值
  //建小堆,使用arr中前K个元素建堆
  int i = 0;
  int top[20] = { 0 };
  for (i = 0; i < 20; i++)
  {
    top[i] = arr[i];
    HeapAdjustdown(top, 0, i);
  }
  //使用剩下的前N-K个元素依次与堆顶元素来比较，不满足则体替代元素
  for (i = 20; i < 1000; i++)
  {
    if (arr[i] > top[0])
    {
      int tmp = arr[i];
      arr[i] = top[0];
      top[0] = tmp;
      HeapAdjustdown(top, 0, 20);
    }
  }
  //打印
  for (i = 0; i < 20; i++)
  {
    printf("%d ", top[i]);
  }
  
  return 0;
}

【数据结构】堆

堆的结构与实现

堆的概念

堆的性质

堆的实现

堆的初始化

堆的调整

堆的向上调整

堆的向下调整

堆的创建

向上调整建堆

向下调整建堆

建堆的时间复杂度

堆的插入

堆的删除

堆的整体代码实现

heap.h

heap.c

堆的应用

堆排序

TOP-K问题

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】堆

堆的结构与实现

堆的概念

堆的性质

堆的实现

堆的初始化

堆的调整

堆的向上调整

堆的向下调整

堆的创建

向上调整建堆

向下调整建堆

建堆的时间复杂度

堆的插入

堆的删除

堆的整体代码实现

heap.h

heap.c

堆的应用

堆排序

TOP-K问题

热门文章

最新文章

相关课程

相关电子书