堆——“数据结构与算法”

typedef int HeapDataType;
typedef struct Heap
{
  HeapDataType* a;
  int size;
  int capacity;
}Heap;

插入数据

需要用到一种特别的算法——向上调整算法

//插入数据
void HeapPush(Heap* php, HeapDataType x)
{
  assert(php);
  //扩容
  if (php->size == php->capacity)
  {
    int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HeapDataType* tmp = (HeapDataType*)realloc(php->a, newcapacity * sizeof(HeapDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    php->a = tmp;
    php->capacity = newcapacity;
  }
  php->a[php->size] = x;
  php->size++;
  AdjustUp(php->a, php->size - 1);
}

//向上调整算法
void AdjustUp(HeapDataType* a, int child)
{
  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 Swap(HeapDataType* p1, HeapDataType* p2)
{
  HeapDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

测试一下向上调整算法和插入数据的功能：

int main()
{
  Heap hp;
  HeapInit(&hp);
  int a[] = { 65,100,70,32,50,60 };
  int sz = sizeof(a) / sizeof(a[0]);
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    HeapPush(&hp, a[i]);
  }
  return 0;
}

删除堆顶的数据

挪动覆盖，不能保证还是堆——父子关系全变了

只能重新建堆

第一种方法：挪动覆盖删除堆顶元素，重新建堆

但是这种方法的代价太大了

第二种方法：首尾数据交换，再删除，再调堆

这种方法就需要用到一种算法——向下调整算法

向下调整算法的前提是：左子树和右子树是大堆/小堆

//向下调整算法
//这边写int* 而不写HeapDataType* 是有意为之的 为以后堆排序作准备
void AdjustDown(int* a, int n, int parent)
{
  //默认左孩子小
  int child = parent * 2 + 1;
  while (child < n)//孩子在数组范围内
  {
    //选出左右孩子中小/大的那一个
    //有可能假设错了
    //左孩子不存在，一定没有右孩子——完全二叉树
    //左孩子存在，有可能没有右孩子
    if ( child + 1 < n && a[child + 1] < a[child])
    //  右孩子存在     右孩子<左孩子
    //不能这么写 if (la[child + 1] < a[chid] && child + 1 < n )
    //这样写会有越界的风险 因为是先访问了数组中的元素 再去比较右孩子是否存在
    {
      ++child;
    }
    //child就是小的那个孩子
    //不关心到底是左孩子还是右孩子 小根堆：和小的孩子比较就可以了
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      child = parent * 2 + 1;//默认又算的是左孩子
    }
    else
    {
      break;
    }
 
  }
}

//删除堆顶数据
void HeapPop(Heap* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  Swap(&php->a[0], &php->a[php->size - 1]);
  php->size--;
  AdjustDown(php->a, php->size, 0);
}

判空

//判空
bool HeapEmpty(Heap* php)
{
  assert(php);
  if (php->size == 0)
  {
    return true;
  }
  else
  {
    return false;
  }
}

堆顶元素和元素个数

//堆顶元素
HeapDataType HeapTop(Heap* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  return php->a[0];
}
//元素个数
int HeapSize(Heap* php)
{
  assert(php);
  return php->size;
}

堆的销毁

//堆的销毁
void HeapDestroy(Heap* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->size = 0;
  php->capacity = 0;
}

测试一下上述功能：

#include"heap.h"
int main()
{
  Heap hp;
  HeapInit(&hp);
  int a[] = { 65,100,70,32,50,60 };
  int sz = sizeof(a) / sizeof(a[0]);
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    HeapPush(&hp, a[i]);
  }
  while (!HeapEmpty(&hp))
  {
    int top = HeapTop(&hp);
    printf("%d\n", top);
    HeapPop(&hp);
  }
  return 0;
}

模拟实现堆的源代码如下：

heap.c的内容：

#include"heap.h"
//堆的初始化
void HeapInit(Heap* php)
{
   assert(php);
   php->a = NULL;
   php->size = 0;
   php->capacity = 0;
}
//堆的销毁
void HeapDestroy(Heap* php)
{
   assert(php);
   free(php->a);
   php->a = NULL;
   php->size = 0;
   php->capacity = 0;
}
//交换数据
void Swap(HeapDataType* p1, HeapDataType* p2)
{
   HeapDataType tmp = *p1;
   *p1 = *p2;
   *p2 = tmp;
}
//向上调整算法
void AdjustUp(HeapDataType* a, int child)
{
   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(Heap* php, HeapDataType x)
{
   assert(php);
   //扩容
   if (php->size == php->capacity)
   {
       int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
       HeapDataType* tmp = (HeapDataType*)realloc(php->a, newcapacity * sizeof(HeapDataType));
       if (tmp == NULL)
       {
           perror("realloc fail");
           return;
       }
       php->a = tmp;
       php->capacity = newcapacity;
   }
   php->a[php->size] = x;
   php->size++;
   AdjustUp(php->a, php->size - 1);
}
//向下调整算法
//这边写int* 而不写HeapDataType* 是有意为之的 为以后堆排序作准备
void AdjustDown(int* a, int n, int parent)
{
   //默认左孩子小
   int child = parent * 2 + 1;
   while (child < n)//孩子在数组范围内
   {
       //选出左右孩子中小/大的那一个
       //有可能假设错了
       //左孩子不存在，一定没有右孩子——完全二叉树
       //左孩子存在，有可能没有右孩子
       if ( child + 1 < n && a[child + 1] < a[child])
       //    右孩子存在            右孩子<左孩子
       //不能这么写 if (la[child + 1] < a[chid] && child + 1 < n )
       //这样写会有越界的风险 因为是先访问了数组中的元素 再去比较右孩子是否存在
       {
           ++child;
       }
       //child就是小的那个孩子
       //不关心到底是左孩子还是右孩子 小根堆：和小的孩子比较就可以了
       if (a[child] < a[parent])
       {
           Swap(&a[child], &a[parent]);
           child = parent;
           child = parent * 2 + 1;//默认又算的是左孩子
       }
       else
       {
           break;
       }

   }
}
//判空
bool HeapEmpty(Heap* php)
{
   assert(php);
   if (php->size == 0)
   {
       return true;
   }
   else
   {
       return false;
   }
}
//删除堆顶数据
void HeapPop(Heap* php)
{
   assert(php);
   assert(!HeapEmpty(php));
   Swap(&php->a[0], &php->a[php->size - 1]);
   php->size--;
   AdjustDown(php->a, php->size, 0);
}
//堆顶元素
HeapDataType HeapTop(Heap* php)
{
   assert(php);
   assert(!HeapEmpty(php));
   return php->a[0];
}
//元素个数
int HeapSize(Heap* php)
{
   assert(php);
   return php->size;
}

heap.h的内容：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HeapDataType;
typedef struct Heap
{
   HeapDataType* a;
   int size;
   int capacity;
}Heap;
//堆的初始化
void HeapInit(Heap* php);
//堆的销毁
void HeapDestroy(Heap* php);
//插入数据
void HeapPush(Heap* php, HeapDataType x);
//向上调整算法
void AdjustUp(HeapDataType* a, int child);
//删除堆顶数据
void HeapPop(Heap* php);
//向下调整算法
void AdjustDown(int* a, int n, int parent);
//判空
bool HeapEmpty(Heap* php);
//堆顶元素
HeapDataType HeapTop(Heap* php);
//元素个数
int HeapSize(Heap* php);

好啦，小雅兰今天的学习内容就到这里啦，下篇博客小雅兰将继续分享二叉树的相关知识点，敬请期待！！！