最小堆中的替换元素

本文介绍了最小堆中的替换元素的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

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

this ques. was asked to my friend in phone interview .

这是我的解决方案，请告诉我我是否正确.

here is my solution , please tell if i am right or not.

解决方案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:

时间复杂度-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;
   }
}

这篇关于最小堆中的替换元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

Heap