最小堆中的替换元素

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

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

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; } }