二叉堆

完全二叉树:每一层的子节点个数必须
叶子节点:没有子节点的节点
第一个非叶子节点:堆元素个数除以2得到的索引就是第一个非叶子节点。count/2(以1开始计数)(count-1)/2(以0开始计数)

节点序号规律:

以1开始计数:每个节点的序号都是父节点序号的2倍,相应的每个节点的左子节点序号都是自身序号的二倍,右子节点序号是自身序号的二倍+1。
parent(i) = i / 2
left child(i) = i 2
right child(i) = i
2 + 1
以0开始计数:
parent(i) = (i - 1) / 2
left child(i) = i 2 + 1
right child(i) = i
2 + 2

最大二叉堆

规则

1.任何一个节点都不大于它的父节点
2.二叉堆是一个完全二叉树

往堆中添加一个元素

把要新加入到堆中的元素添加到堆的尾部,然后以尾部的位置开始执行shiftUp操作,shiftUp操作过程如下:
判断当前节点是否比其父节点大,如果比父节点大并且当前节点序号大于1(以1开始计数)就跟父节点交换位置。一直循环该操作。

在堆中取出一个元素

把堆中根节点的元素取出来然后再把尾节点的元素移到根节点的位置后对根节点做做shiftDown操作
shiftDown操作过程如下:

Heapify

将一个数组建立成一个最大堆的形状的过程叫做Heapify

命令模式
You need to set install_url to use ShareThis. Please set it in _config.yml.

评论

You forgot to set the shortname for Disqus. Please set it in _config.yml.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×