Y********f
发帖数: 410 | 1 面试中问到的heap是指数组结构(A[i]的children是A[2*i], A[2*i+1])呢，还是树结构
？如果是树结构，是不是BFS中前面的节点都是两个children？
最近看了两道题有关heap的题都有点无从下手：
1.Convert a min heap to BST without changing its structure and of course no
extra space(感觉这道题中heap是树结构）。
2.Convert a max heap to min heap.
谁来给点思路？ | n****r
发帖数: 120 | 2 第二题可以从N/2出向根节点遍历，使得当前子树为minHeap。换句话说，从N/2处向前
遍历，将当前节点做下沉操作
public void toMinHeap(){
for(int i=N/2; i>=1; i--){
int k = i;
while(2*k<=N){
int j = 2 * k;
if(j+1 <= N && less(j+1,j)) j++;
if(less(k,j)) break;
exch(j,k);
k = j;
}
}
} |
|
