大家好，又见面了，我是你们的朋友全栈君。
优先队列（堆）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
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/160504.html原文链接：https://javaforall.net
