计数二进制堆中的交换

Question

从1到n的数字按照一定的顺序加入到最小堆中。对于每个数字，找出它在最小堆中改变位置的次数。

澄清：添加使用方法 Insert()，按照输入中的相同顺序添加节点。

输入: 第一行是数字n。第二行，用空格隔开，是n个数字，从1到n.

输出：n个数除以空格：第i个数表示第i个数在构造的min-heap中的位置变化次数。

即5 4 3 2 1

答案 2 3 3 2 2

public class MinHeap {
private int[] heap;
private int size;
private int maxsize;

public MinHeap(int maxsize) {
    this.maxsize = maxsize;
    this.size = 0;
    heap = new int[this.maxsize + 1];
    heap[0] = Integer.MIN_VALUE;
}

private void swap(int fpos, int spos) {
    int tmp;
    tmp = heap[fpos];
    heap[fpos] = heap[spos];
    heap[spos] = tmp;
}

private void minHeapify(int pos) {
    if (2 * pos == size) {
        if (heap[pos] > heap[2 * pos]) {
            swap(pos, 2 * pos);
            minHeapify(2 * pos);
        }
        return;
    }

    if (2 * pos <= size) {
        if (heap[pos] > heap[2 * pos] || heap[pos] > heap[2 * pos + 1]) {
            if (heap[2 * pos] < heap[2 * pos + 1]) {
                swap(pos, 2 * pos);
                minHeapify(2 * pos);
            }
            else {
                swap(pos, 2 * pos + 1);
                minHeapify(2 * pos + 1);
            }
        }
    }
}

public void insert(int element) {
    heap[++size] = element;
    int current = size;

    while (heap[current] < heap[current / 2]) {
        swap(current, current / 2);
        current = current / 2;
    }
}

public void minHeap() {
    for (int pos = (size / 2); pos >= 1; pos--) {
        minHeapify(pos);
    }
}

public int extractMin() {
    if (size == 0) {
        throw new NoSuchElementException("Heap is empty");
    }
    int popped = heap[1];
    heap[1] = heap[size--];
    minHeapify(1);
    return popped;
}

}

我不懂怎么数

Answer 1

评论后更新

我不知道你是怎么得到输出“0 1 2 2 3”的。我会期待“0 1 1 2 2”。但现在已经无关紧要了。

我明白我误解了你原来的问题。您不需要插入每个项目时的交换次数。您想知道在堆的整个生命周期中每个项目改变位置的次数。

您需要构建一个映射，其中键是项目的值，值部分是项目参与交换操作的次数。在您的 swap 方法中，您检查地图以查看该项目是否存在。如果该项目不存在于地图中，则将其添加到计数 1。如果它确实存在，则增加其计数。

完成向堆中添加项目后，您可以打印地图的内容。

原回答

您可以有一个名为 numSwaps 的 class 变量：

private int numSwaps;

然后在你的 swap 方法中，只要有交换就增加它：

private void swap(int fpos, int spos) {
    int tmp;
    tmp = heap[fpos];
    heap[fpos] = heap[spos];
    heap[spos] = tmp;
    numSwaps = numSwaps + 1;
}

并提供方法clearSwaps（重置为0）和getSwaps（重置为return当前交换次数）。

计数二进制堆中的交换

Count swaps in Binary Heap

java

heap

binary