从最大堆中的任意位置移除一个元素

Question

我有一个只有 x 和 y 的点对象，我有一个堆数据结构，如下所示：

class MaxHeap{
public Point[] heap;
public int size;
public int maxsize;

public MaxHeap(int maxsize){
    this.maxsize = maxsize;
    this.size = 0;
    heap = new Point[this.maxsize+1];
    heap[0] = new Point(-1,-1); //Heap is empty
}

public int parent(int pos){
    return pos /2;
}

public int leftChild(int pos){
    return (2 * pos);
}

public int rightChild(int pos){
    return (2 * pos) +1;
}

public boolean isLeaf(int pos){
    if (pos >= (size / 2) && pos <= size){
        return true;
    }
    return false;
}

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

public void maxHeapify(int pos){
    if (!isLeaf(pos)){
        if (heap[pos].getY() < heap[leftChild(pos)].getY() || heap[pos].getY() < heap[rightChild(pos)].getY()){
            swap(pos, leftChild(pos));
            maxHeapify(leftChild(pos));
        }
        else{
            swap(pos, rightChild(pos));
            maxHeapify(rightChild(pos));
        }
    }
}

public void insert (Point p){
    heap[++size] = p;
    int current = size;
    while (heap[current].getY() > heap[parent(current)].getY()){
        swap(current, parent(current));
        current = parent(current);
    }
}

我正在尝试实现一种从堆中删除任何点的方法，而不是传统的删除方法，它只是删除顶部。我不完全确定该怎么做。我在想我可以将 Point 的索引存储在 Point 内部的堆中。我不确定这是否有帮助。

Answer 1

就是这样，您是否知道 Java 中有一个名为 PriorityQueue 的标准堆实现？ removeAt(int i)的实现方式可以作为参考。

回到你的问题。

为了从队列中移除中间元素，您需要用队列的最后一个元素替换它（将队列缩小一个元素）并尝试 "heapify" 这个元素。如果元素仍然存在（两个子元素都比元素大），则需要 "heapify" 向上移动。

关于你问题的第二部分。我不建议在 Point class 中存储队列索引，从而使点队列感知。更好的方法是维护一个从point到它在队列内部的索引的Map（这个map可以用IdentityHashMap[Point, Integer]来表示）。当您在队列中进行更改时，例如插入、删除元素、交换元素等，请不要忘记在此映射中进行适当的更改。

Answer 2

这是一个答案:

     public void removeSpecificElement(int i) {
        heap[i] = heap[size];
        size--;
        while (getParent(i) < heap[i] && i > 1 ) {
            swapElements(heap[i], getParent(i));
            i = getParent(i);
        }

        heapifyUp(i);

    }

从最大堆中的任意位置移除一个元素

Remove an element from any position in a max heap

java

max-heap