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

简介: 堆——“数据结构与算法”

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


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


相关文章
|
5天前
|
存储 JavaScript 前端开发
什么是堆?什么是栈?他们之间从区别和联系
什么是堆?什么是栈?他们之间从区别和联系
34 0
|
5天前
|
存储 缓存 算法
堆和栈的概念和区别
堆和栈的概念和区别
19 1
|
5天前
|
存储 算法
【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典)
【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典)
32 0
|
5天前
|
算法
数据结构之堆的结构与实现
数据结构之堆的结构与实现
|
5天前
|
存储 机器学习/深度学习 算法
数据结构与算法:堆
朋友们大家好啊,本篇文章来到堆的内容,堆是一种完全二叉树,再介绍堆之前,我们首先对树进行讲解
数据结构与算法:堆
|
5天前
|
存储 程序员
什么是堆,什么是栈
什么是堆,什么是栈
7 0
|
5天前
|
Arthas 监控 算法
JVM工作原理与实战(二十五):堆的垃圾回收-垃圾回收算法
JVM作为Java程序的运行环境,其负责解释和执行字节码,管理内存,确保安全,支持多线程和提供性能监控工具,以及确保程序的跨平台运行。本文主要介绍了垃圾回收算法评价标准、标记清除算法、复制算法、标记整理算法、分代垃圾回收算法等内容。
22 0
JVM工作原理与实战(二十五):堆的垃圾回收-垃圾回收算法
|
5天前
【数据结构】二叉树-堆(top-k问题,堆排序,时间复杂度)
【数据结构】二叉树-堆(top-k问题,堆排序,时间复杂度)
18 4
|
5天前
【数据结构】二叉树-堆(函数实现)
【数据结构】二叉树-堆(函数实现)
13 2
|
5天前
|
存储 C语言
数据结构:8、堆
数据结构:8、堆
21 0