二进制堆中的计数交换

Question

从1到n的数字以一定顺序添加到最小堆中。对于每个数字，找出其在最小堆中的位置更改了多少次。

Clarification：对于添加方法，使用Insert（），以与输入中相同的顺序添加节点。

输入：第一行是数字n。在第二行中，除以空格，是从1到n的n个数字。

输出：n个数字除以空格：第i个数字表示在构造的最小堆中i的位置变化数。

即5 4 3 2 1

answer 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

您可能有一个名为numSwaps的类变量：

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（返回交换的当前数量）。