Heapify a Binary tree - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Heapify a Binary tree

Heapify a Binary tree# JobHunting - 待字闺中

R*y2012-12-11 08:12

1 楼

如何Heapify a Binary tree?
我google了一些资料，大部分的思路都是将binary tree 存储到一个数组，然后进行
heapify. 默认这个二叉树是用Node表示。
但是二叉树转换成数组的过程中，需要遍历两次这个树，第一次获得节点数目，第二次
存储节点。这就是2*O(n)了。
板上各位有没有其他的方法，直接在树本身上进行heapify?
谢谢各位

h*e2012-12-11 08:12

2 楼

。。只一次吧。放到vector裏面。

【在 R**y 的大作中提到】

: 如何Heapify a Binary tree?
: 我google了一些资料，大部分的思路都是将binary tree 存储到一个数组，然后进行
: heapify. 默认这个二叉树是用Node表示。
: 但是二叉树转换成数组的过程中，需要遍历两次这个树，第一次获得节点数目，第二次
: 存储节点。这就是2*O(n)了。
: 板上各位有没有其他的方法，直接在树本身上进行heapify?
: 谢谢各位

R*y2012-12-11 08:12

3 楼

用collection 的话确实只要一次就能存储进去。
我一直在想能否直接操作，避免这样的过度

【在 h*******e 的大作中提到】

: 。。只一次吧。放到vector裏面。