大家好，又见面了，我是你们的朋友全栈君。
优先队列（堆）priority queue
- 完全二叉树：除了最底层都被元素填满
- 堆序性：除根节点，最小堆每个节点父亲的Key小于等于该节点的Key，最大堆反之
优先队列的申明
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
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/160504.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
