数据结构之堆详解

简介: 数据结构之堆详解

1.什么是堆

知道以上的存储方法,对于完全二叉树,有一个叫做堆的结构,堆本质就是一个完全二叉树,

堆分两种:1.大堆    2.小堆

除了是完全二叉树,大堆需满足任何一个双亲都大于等于孩子,对于小堆,任何一个双亲都小于等于孩子。

d6a453d84d494c2dbaaf71de58fd1d19.png

堆的定义

我们实现堆就用数组来实现的:这里以实现小堆为例

结构体定义与函数接口

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int HPDATAtype;
typedef struct Heap
{
  HPDATAtype *a;
  int size;
  int capacity;
}HP;
void Heapinit(HP* f);
void Heapdestroy(HP* f);
void Heappop(HP* f);
void Heappush(HP* f , HPDATAtype x);

堆的初始化

void Heapinit(HP* f)
{
  //初始有4个空间
  assert(f);
  f->a = NULL;
  f->size = 0;
  f->capacity = 0;
}

堆的销毁

void Heapdestroy(HP* f)
{
  assert(f->a);
  free(f->a);
  f->a = NULL;
}

入堆

void Heappush(HP* f, HPDATAtype x)
{
  assert(f);
  if (f->capacity == f->size)
  {
  int  newcapacity = f->capacity = 0 ? 4 : f->capacity*2;
      HPDATAtype* newnode = (HPDATAtype*)malloc(newcapacity);
  if (newnode == NULL)
  {
    perror("扩容失败\n");
    return;
  }
  f->a = newnode;
  f->capacity = f->capacity*2;
  }
  f->a[f->size] = x;
  f->size++;
  //向上调整算法
  Adjustup(f->a, f->size - 1);
  //向下调整算法
  //Adjustdown(f->a, f->size - 1);
}

在这里在入堆之后,也就是元素赋值到数组之后,根据你对数组的调整,也就是所说的向上调整算法,和向下调整算法,决定是小堆,还是大堆。

向上调整算法

我们这里通过对树所对应的数组元素的关系寻找父亲。 小堆:

void Adjustup(HPDATAtype*a, int child)
{
  //根据孩子zhaofuqin
  int parent = (child - 1) / 2;
  while (child>0)
  {
    if ( a[child]<a[parent])
    {
      HPDATAtype p = a[child];
      a [child] = a[parent];
      a[parent]=p;
      child = parent;
      parent = (child - 1) / 2;
    }
    else 
    {
      break;
    }
  }
}

大堆

这里只需要更改判断条件就变成大堆的调整

void Adjustdown(HPDATAtype* a, int child)
{
  //根据孩子找父亲
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    if (a[child] > a[parent])
    {
      int tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp; 
        child = parent;
    parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

出堆

出堆就是最后一个元素换到第一个元素,在size--,之后在进行调整。

void Heappop(HP* f){
  assert(f);
  //堆顶元素出堆,最后元素出堆
  assert(f->size);
  int tmp = f->a[0];
  f->a[0] = f->a[f->size - 1];
  f->a[f->size - 1] = tmp;
  f->size--;
  //向下调整
  Adjustdown(f->a, f->size, 0);
};

向下调整算法

出堆为了不改变原有的父节点与兄弟节点的关系,采用的是将堆底的最后一个与第一个互换,在减减,此时我们仍需要调整堆,采用向下调整算法---即从第一个节点处开始,找作为父节点的儿子节点中较小的那一个,两者比较,循环调整。

因此传参需要堆的大小以及第一个父亲结点坐标也就是0.

void Adjustdown(HPDATAtype* a, int size,int parent)
{
  int child =parent * 2 +1;
  while (child<size)
  {
    if ((child+1<size)&&a[child + 1] < a[child])//若右孩子存在且小于左孩子
    {
      ++child;
    }
    if (a[child] < a[parent])
    {
      //交换
      int tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp;
      parent = child;
      child = parent * 2 + 1;
    }else
    {
      break;
    }
  }
}

返回堆顶元素

HPDATAtype HeapTop(HP* f)
{
  assert(f);
  assert(!HeapEmpty(f));
  return f->a[0];//返回堆顶数据
}

判空

bool HeapEmpty(HP* f)
{
  if (f->size == 0)
  {
    return true;
  }
  else
  {
    return false;
  }
}

堆的应用

.堆可以用作优先级队列,实现高效的插入和删除操作

.堆可以用来解决海量数据的topk问题,即从大量数据中找出最大或最小的k个数

.堆可以用来进行堆排序,即每次把堆顶元素和堆尾元素交换,然后重新调整堆,直到堆为空

.堆还可以用来实现一些其他的算法,比如哈夫曼编码,Dijkstra算法等

需要注意的是对于向上排序算法还是向下排序算法,他们都是一对一对的使用,从而取决于你是大堆还是小堆,主要体现调整算法中的判断条件。

相关文章
|
7天前
|
存储 算法
【数据结构】堆
【数据结构】堆
|
1月前
|
算法 安全 大数据
揭秘!Python堆与优先队列:数据结构的秘密武器,让你的代码秒变高效战士!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue提供堆与优先队列功能,助你提升算法效率。堆用于快速找大数据集的第K大元素,如示例所示,时间复杂度O(n log k)。PriorityQueue在多线程中智能调度任务,如模拟下载管理器,按优先级处理任务。掌握这些工具,让代码运行更高效!
49 1
|
6天前
|
存储 算法 Linux
【数据结构】树、二叉树与堆(长期维护)(1)
【数据结构】树、二叉树与堆(长期维护)(1)
|
12天前
|
搜索推荐 算法 Go
深入探索堆:Go语言中的高效数据结构
深入探索堆:Go语言中的高效数据结构
|
6天前
|
算法
【数据结构】树、二叉树与堆(长期维护)(2)
【数据结构】树、二叉树与堆(长期维护)(2)
【数据结构】树、二叉树与堆(长期维护)(2)
|
12天前
【数据结构】二叉树顺序实现(大堆)-->赋源码
【数据结构】二叉树顺序实现(大堆)-->赋源码
26 4
|
1月前
|
存储 算法
【数据结构】堆,堆的实现,堆排序,TOP-K问题
数据结构——堆,堆的实现,堆排序,TOP-K问题
22 1
【数据结构】堆,堆的实现,堆排序,TOP-K问题
|
1天前
|
算法
【初阶数据结构篇】堆的应用(堆排序与Top-K问题)
即求数据结合中前K个最⼤的元素或者最⼩的元素,⼀般情况下数据量都⽐较⼤。
|
1天前
|
存储 算法 测试技术
【初阶数据结构篇】实现顺序结构二叉树(堆的实现方法)
注意传过去的参数是插入的位置,即插入前的size,在调整完后再将size++
|
5天前
|
存储
全局变量和局部变量在堆和栈的区别
全局变量和局部变量在堆和栈的区别
17 0