这个问题.在电话采访中被邀请给我的朋友.
this ques. was asked to my friend in phone interview .
实现一个函数,该函数将在min-heap中将索引 i 处的元素替换为 k ,并重新排列回堆.
Implement a function that will replace element at index i by k , in min-heap and rearrange heap back .
这是我的解决方案,请告诉我我是否正确.
here is my solution , please tell if i am right or not.
解决方案1:
1)堆[i] = k 2)heapify(heap,1)
1)heap[i]=k 2) heapify(heap , 1)
但这在这种情况下似乎是错误的:
but this seems to be wrong as in this case :
10 / \ 14 59 (<-was 12 before replacing) .. / \ 55 20所以在这里我们交换(55,59),但仍然会破坏min-heap属性.
so here we swap(55,59) but still min-heap property will be voilated.
解决方案2:
1)用堆[最后一个索引]替换堆[i] 2)heapify(heap,1)3)现在像往常一样在堆中插入
1)replace heap[i] by heap[last index] 2) heapify(heap , 1) 3) now insert as usual procedure in heap
时间复杂度-O(log N)(解决方案2 )是正确的方法吗?如果没有,请给出一些提示.
time complexity - O(log N) is it (solution 2) the correct approach ? if not please give some hints .
推荐答案解决方案1之类的方法可能更好.
Something like solution 1 is probably better.
- heap [i] = k
- 如果 heap [i] 小于其父对象,则将其冒泡(游泳)
- 否则,如果 heap [i] 大于其子级之一,则将其冒泡(下沉)
- heap[i] = k
- If heap[i] is smaller than its parent, bubble it up (swim)
- Otherwise, if heap[i] is larger than one of its children, bubble it down (sink)
运行时间: O(log n).
要游泳-当它小于其父项时,将其与父项交换.
To swim - While it's smaller than its parent, swap it with its parent.
沉没-当它大于其子项之一时,将其与最小的子项交换.
To sink - While it's larger than one of its children, swap it with its smallest child.
用于和接收器的某些Java代码,取自此处:
private void swim(int k) { while (k > 1 && less(k/2, k)) { exch(k, k/2); k = k/2; } } private void sink(int k) { while (2*k <= N) { int j = 2*k; if (j < N && less(j, j+1)) j++; if (!less(k, j)) break; exch(k, j); k = j; } }更多推荐
最小堆中的替换元素
发布评论