锐客网

  1. 首页 > 睿知 > it技术 > >

数据结构之堆（优先级队列）

IT知识优先级优先级队列

志不强者智不达，言不信者行不果。这篇文章主要讲述数据结构之堆（优先级队列）相关的知识，希望能为你提供帮助。
?
写在前面数据结构很久没有更新了，这些天一直在作二叉树的的题目，对我来说有些难，心里面感觉有些烦躁，就一直没有很大家分享知识。今天要说的是关于堆的内容，知识点不多。我们为了更好的理解，我通过C语言来模拟实现它的基础逻辑，由于在java中封装了这个数据构，堆的叫做优先级队列，我一并说一说它的用法，并且看看IEDA的部分源码。总体而言，还是有一定的难度的，但我相信，如此帅的读者一定会掌握的。
初始堆谈到堆就不的提一下二叉树，在众多二叉树中，有一个最基本的，也是很重要的叫做完全二叉树，完全二叉树可以理解为从根节点开始标号，从0开始，每一层从左往有按照树的节点依次标记，不会出现节点跳跃的树。

数据结构之堆（优先级队列）

文章图片

我们都是知道，树是一个非线性的结构，它数据存储的空间并不连续，我们是否可以有一个做法使得完全二叉树中的数据集中起来。堆就是这个结构。
  • 堆的物理结构是一个数组
  • 堆的逻辑结构是一个完全二叉树
堆如何存储树中的数据堆的存储数据方式是层序遍历，我们一层一层的将数据放到数组中。不过我们这里不会说数的遍历，这里今天谈二叉树就是我了辅助理解我们今天的堆，辅助我们如何建立堆。
数据结构之堆（优先级队列）

文章图片

堆的性质堆有很多优良特性，在谈之前，我们先说说堆的分类


堆分为两种


  1. 大堆 （大根堆） 双亲节点存储的数据大于孩子节点存储的数据
  2. 小堆 （小根堆） 双亲节点存储的数据小于孩子节点存储的数据
关于堆的特性我们也要谈一谈，如果我们把根节点的下标标为 0 ，要是我们给出一个下标为 i，的节点，我们就可以得到它的双亲结点和孩子节点的下标（要是存在的话）
  • 双亲结点 （i - 1） / 2
  • 左孩子 2 × i + 1 右孩子 2 × i + 2
建堆理论知识我们需要了解这么多就可以了，下面开始的都是我们的实际操作。我们以建小堆为例吧，只要学会了小堆，大堆也不在话下了。
我们需要一个结构体来辅助我们完成任务，一起看看吧
#pragma once
#include < stdio.h>
#include < assert.h>
#include < stdlib.h>
#include < stdbool.h>

typedef int HPDataTytpe;

struct Heap

HPDataTytpe* elem; // 指针
size_t szie; // 数组的有限元素的个数
size_t capacity; // 数组的空间大小
;

我们要写下面几个函数，明白了这些函数的原理，我们就可以掌握了堆了
//初始化堆
void HeapInit(Heap* php);

//销毁 堆
void HeapDestroy(Heap* php);

//数据入堆
void HeapPush(Heap* php, HPDataTytpe val);

//数据出堆
void HeapPop(Heap* php);

//判断堆是不是 空
bool HeapEmpty(Heap* php);

//向上调整
void adjustUp(HPDataTytpe* elem, int size);

//向下调整
void adjustDown(HPDataTytpe* elem, int size,size_t root);

初始化堆& 销毁堆这个很简单，我们就不说了，我把代码放在下面了。
void HeapInit(Heap* php)

assert(php);
php-> elem = NULL;
php-> capacity = 0;
php-> szie = 0;

void HeapDestroy(Heap* php)

assert(php);
free(php-> elem);
php-> elem = NULL;
php-> capacity = 0;
php-> szie = 0;

数据入堆这个才是我们今天的硬菜之一，最好吃的就是里面的向上调整，对于void HeapPush(Heap* php, HPDataTytpe val); 函数，我们把数据放在数组的最后面，不过这个数组还一定是小堆吗？不一定的，我们需要进行向上调整才能让它仍旧保持成一个小堆。
void HeapPush(Heap* php, HPDataTytpe val)

assert(php);
//判满
if (php-> capacity == php-> szie)

size_t newSize = (php-> capacity == 0) ? 4 : 2 * (php-> capacity);
HPDataTytpe* pCur = (HPDataTytpe*)realloc(php-> elem, sizeof(HPDataTytpe)*newSize);
assert(pCur);
php-> elem = pCur;
php-> capacity = newSize;


php-> elem[php-> szie++] = val;
adjustUp(php-> elem, php-> szie); // 向上调整

向上调整
当我们数据进入数组后，不一定还是一个堆了，所以我们要通过向上调整使得它仍旧保持一个堆，下面是向上调整的原理图


数据结构之堆（优先级队列）

文章图片

void swap(HPDataTytpe* pa, HPDataTytpe*pb)

assert(pa& & pb);
HPDataTytpe ret = *pa;
*pa = *pb;
*pb = ret;


void adjustUp(HPDataTytpe* elem, int size)

assert(elem);
int child = size - 1;
int parent = (child - 1) / 2;
while (child > 0)//判断条件很重要

if (elem[child] < elem[parent])

swap(& elem[child], & elem[parent]); // 交换 这两个数

else

break;

child = parent;
parent = (child - 1) / 2;


【数据结构之堆（优先级队列）】通过上面我们就可以建立一个小堆了，用代码试试
int main()

Heap heap;
HeapInit(& heap);
HeapPush(& heap, 3);
HeapPush(& heap, 5);
HeapPush(& heap, 6);
HeapPush(& heap, 10);
HeapPush(& heap, 0);

for (int i = 0; i < (int)heap.szie; i++)

printf("%d ", heap.elem[

    推荐阅读


    上一篇：[OpenCV实战]19 使用OpenCV实现基于特征的图像对齐

    下一篇：Redis 进阶 -- 搭建主从复制及哨兵模式集群