前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >优先队列(堆)priority queue

优先队列(堆)priority queue

作者头像
全栈程序员站长
发布2022-09-13 10:25:50
2620
发布2022-09-13 10:25:50
举报
文章被收录于专栏:全栈程序员必看

大家好,又见面了,我是你们的朋友全栈君。

优先队列(堆)priority queue

  • 完全二叉树:除了最底层都被元素填满
  • 堆序性:除根节点,最小堆每个节点父亲的Key小于等于该节点的Key,最大堆反之
优先队列的申明
代码语言:javascript
复制
struct HeapStruct;
typedef struct HeapStruct* PriorityQueue;

PriorityQueue Initialize (int MaxElements);
void Destroy (PriorityQueue H);
void MakeEmpty (PriorityQueue H);
void Insert (ElementType X, PriorityQueue H);
ElementType DeleteMin (PriorityQueue H);
ElementType FindMin (PriorityQueue H);
int IsEmpty (PriorityQueue H);
int IsFull (PriorityQueue H);

struct HeapStruct
{
	int Capacity;
	int size;
	ElementType* Elements;
}
Insert

插入操作,将新增元素放到最后面,比较其与父节点,进行上滤,O(logN)

DeleteMin

删除操作,删除根节点元素后,进行下滤,O(logN)

FindMin

根元素即为所求,O(1)

应用

求第k大的数,求最大前k个数,klogN

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/160504.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 优先队列(堆)priority queue
    • 优先队列的申明
      • Insert
      • DeleteMin
      • FindMin
    • 应用
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档