最小堆中的替换元素 [英] replacing element in min-heap

问题描述

这个问题.在电话采访中被邀请给我的朋友.

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代码，取自 查看全文