f*z
发帖数: 34 | 1 careercup上看到的，没有想到好的办法。
题目：
Convert a min heap to BST without changing its structure and
of course no extra space |
S******n
发帖数: 1009 | 2 min heap->linkedlist->BST
structure and
【在 f*z 的大作中提到】
: careercup上看到的，没有想到好的办法。
: 题目：
: Convert a min heap to BST without changing its structure and
: of course no extra space
|
h**i
发帖数: 54 | 3 如果不破坏,我觉得没有额外空间不行吧.
【在 f*z 的大作中提到】
: careercup上看到的，没有想到好的办法。
: 题目：
: Convert a min heap to BST without changing its structure and
: of course no extra space
|
f*z
发帖数: 34 | 4 你的意思是这个heap是链接起来的，而不是通常的用一个array表示的？
【在 S******n 的大作中提到】
: min heap->linkedlist->BST
:
: structure and
|
f*z
发帖数: 34 | 5 我觉得意思是heap跟BST都是binary tree, 保持structure只是保持树形，里面的内容
当然移动了。
【在 h**i 的大作中提到】
: 如果不破坏,我觉得没有额外空间不行吧.
|
S******n
发帖数: 1009 | 6 yes
【在 f*z 的大作中提到】
: 你的意思是这个heap是链接起来的，而不是通常的用一个array表示的？
|
g*********s
发帖数: 1782 | 7 then how to ensure the heap operations' complexity is still O(logN)? for
linked list you can't randomly access the element.
why not assuming the heap is also a binary tree? the array format of heap
is just a compact representation of heap.
even if the input heap is represented as an array, we can still store the
newly bst to the array. but it would need O(1) space for array element
swap. i think this is OK.
【在 S******n 的大作中提到】
: yes
|
f*z
发帖数: 34 | 8 这个链接是二叉树的链接法，就是node有left child, right child, parent指针。
所以operation仍然是O(logN).
对于用array表示的heap和BST, 怎么样来转换呢？
【在 g*********s 的大作中提到】
: then how to ensure the heap operations' complexity is still O(logN)? for
: linked list you can't randomly access the element.
: why not assuming the heap is also a binary tree? the array format of heap
: is just a compact representation of heap.
: even if the input heap is represented as an array, we can still store the
: newly bst to the array. but it would need O(1) space for array element
: swap. i think this is OK.
|
v*******7
发帖数: 187 | 9
对，如果heap用binary tree来表示，那么需要有parent指针的信息，in place可以做
，我这里刚
才想了一个算法，是O(nlgn)的做法，可以做到。
我在想用array表示的heap转换成array 表示的BST要怎么做。
【在 f*z 的大作中提到】
: 这个链接是二叉树的链接法，就是node有left child, right child, parent指针。
: 所以operation仍然是O(logN).
: 对于用array表示的heap和BST, 怎么样来转换呢？
|
v*******7
发帖数: 187 | 10
Sorry，呵呵，刚明白过来，要是用array表示的heap，那做起来更简单，因为不需要用
到parent
指针了，其他都一样，那么time complexity还是O(nlgn),也是inplace的。
【在 f*z 的大作中提到】
: 这个链接是二叉树的链接法，就是node有left child, right child, parent指针。
: 所以operation仍然是O(logN).
: 对于用array表示的heap和BST, 怎么样来转换呢？
|
|
|
f*z
发帖数: 34 | 11 分享一下算法吧
【在 v*******7 的大作中提到】
:
: Sorry，呵呵，刚明白过来，要是用array表示的heap，那做起来更简单，因为不需要用
: 到parent
: 指针了，其他都一样，那么time complexity还是O(nlgn),也是inplace的。
|
t****0
发帖数: 235 | 12 do you have to call
getMin n times to get the linked list?
that is nlgn
I think it does not matter if pointer or array is used to represent the
heap right?
【在 S******n 的大作中提到】
: min heap->linkedlist->BST
:
: structure and
|
t****0
发帖数: 235 | 13 this is more like
heap -> sorted array -> bst
【在 t****0 的大作中提到】
: do you have to call
: getMin n times to get the linked list?
: that is nlgn
: I think it does not matter if pointer or array is used to represent the
: heap right?
|
S******n
发帖数: 1009 | 14 you mean you can use array to represent bst?
【在 t****0 的大作中提到】
: this is more like
: heap -> sorted array -> bst
|
b*******s
发帖数: 5216 | 15 heap sorting O(nlogn)
然后就可以说这是BST了
root是n/2的点
左child是 n/4 ,右child是3n/4
一路二分下去
仅仅是各层节点没有按顺序存放而已 |
f*******4
发帖数: 1401 | 16 heap sort需要额外空间吧？
【在 b*******s 的大作中提到】
: heap sorting O(nlogn)
: 然后就可以说这是BST了
: root是n/2的点
: 左child是 n/4 ,右child是3n/4
: 一路二分下去
: 仅仅是各层节点没有按顺序存放而已
|
f*******4
发帖数: 1401 | 17 如果是用array，排序后，怎么不用额外空间构建BST？ |
C***y
发帖数: 2546 | 18 why not quick sort on the heap?
这样的话还是O(nlogn),但是不需要额外空间
———————————————————
俺错了，heap sort是O（1）的空间
【在 b*******s 的大作中提到】
: heap sorting O(nlogn)
: 然后就可以说这是BST了
: root是n/2的点
: 左child是 n/4 ,右child是3n/4
: 一路二分下去
: 仅仅是各层节点没有按顺序存放而已
|
f*******4
发帖数: 1401 | 19 对 但是sort后怎么倒腾成表示bst的array？
比如
1 2 3 4 5 6 7
变成
4 2 6 1 3 5 7
？
【在 C***y 的大作中提到】
: why not quick sort on the heap?
: 这样的话还是O(nlogn),但是不需要额外空间
: ———————————————————
: 俺错了，heap sort是O（1）的空间
|
C***y
发帖数: 2546 | 20 你就可以当它是bst
4是root，2是左子树的root，6是右子树的root。。。。
不知道有没有这么表示的
【在 f*******4 的大作中提到】
: 对 但是sort后怎么倒腾成表示bst的array？
: 比如
: 1 2 3 4 5 6 7
: 变成
: 4 2 6 1 3 5 7
: ？
|
|
|
f*******4
发帖数: 1401 | 21 不能吧。。。。
【在 C***y 的大作中提到】
: 你就可以当它是bst
: 4是root，2是左子树的root，6是右子树的root。。。。
: 不知道有没有这么表示的
|
t****0
发帖数: 235 | 22 Yes -
The result of heapsort is a sorted array (no need of extra space)
and bst can be represented by array
http://discuss.joelonsoftware.com/default.asp?interview.11.6646
is this an efficient representation...
【在 S******n 的大作中提到】
: you mean you can use array to represent bst?
|
z***e
发帖数: 5393 | 23 我觉得，基本上意思是把每次sort后的结果，提出root（middle value）来，然后对左
右sub tree调整后recursive地反复找root.关键在于对left/right tree的调整。
1
2 3
4 5 6 7
step 1: 交换a[0]和a[middle],也就是a[0]和a[3]交换变成 4 2 3 1 5 6 7
4
2 3
1 5 6 7
注意到 a[middle+1...n/2+1]（left tree在middle value之后的所有siblings）都>
root，同时right tree中a[n/2+2]之前的都小于root，所以要对换value变成
4
2 5
1 3 6 7
（你用一个较大的array比如1 2 3 ....15，比较容易看出来）
然后对left/right各自repeat上述步骤。
【在 f*******4 的大作中提到】
: 对 但是sort后怎么倒腾成表示bst的array？
: 比如
: 1 2 3 4 5 6 7
: 变成
: 4 2 6 1 3 5 7
: ？
|
