heap_堆_PriorityQueues

一、概念

1.  Priority Queues:即带有优先级的队列(先进先出),较好实现方式:大根堆,或小根堆。

2.  堆总是满足下列性质:

a.  堆中某个节点的值总是不大于或不小于其父节点的值;

b.  堆总是一棵完全二叉树。

将根节点最大的堆叫做大根堆,根节点最小的堆叫做小根堆(binary min-heap (minimum key is at the root))。

3.  满二叉树与完全二叉树:

如果一棵二叉树的结点要么是叶子结点,要么它有两个子结点,这样的树就是满二叉树。

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

二、堆 -> 数组

“堆”存储在数组中,某个 i(数组下标)节点的孩子的数组下标为:i * 2,i * 2 + 1,例如:

X   T O   G S M N    A E R A I B

1   2 3     4 5 6 7     8 9 10 11 12    (数组下标从1开始,也可以从0开始)

三、downheap() 与 upheap()

1.  downheap() -> O(log n)

删除 root -> 堆的最后一个节点替换 root -> "修复堆",root如果有必要与"子节点"交换 -> 被改变的子节点继续"修复堆"

2. upheap()-> O(log n)

插入一个节点到堆的最后 ->  "修复堆",该节点如果有必要与"父节点"交换 -> 被改变的父节点继续 "修复堆"

四、堆 -> 构造

1. downheap() -> O(n)

bottom-up heap construction 自下而上堆的构造

自下而上,从右至左的方向,找到第一个“非叶子节点”,如果有必要与"子节点"交换(如果左右节点相等,交换任意一个都可)

即用 downleap() 方法,对每一个子堆

2. upheap() -> O(n log n)

一个一个节点增加到堆的最后 -> 用 upheap() 方法"修复堆"

五、堆排序

堆排序:O(n log n)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容