2

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

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 内部的堆中。我不确定这是否有帮助。

4

2 回答 2

1

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

回到你的问题。

为了从队列中删除中间元素，您需要将其替换为队列的最后一个元素（将队列缩小一个元素）并尝试将这个元素“堆积”下来。如果元素仍然存在（两个孩子都比元素大），您需要“堆积”它。

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

于 2015-09-24T01:40:46.843 回答
0

这是一个答案：

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

    }
于 2021-06-18T06:57:05.443 回答