java - minHeap 作为二叉树

Question

我正在尝试将堆实现为二叉树。我需要在 O(log n) 时间内执行插入和删除功能。它只需要删除最低、最右边的节点。这是我到目前为止的 remove 函数（它是 O(n) 运行时）：

    public Node removeLast() {
        Node k = findLastForDeletion(this.root,1, findHeightforDeletion());
        if (k.parent != null && k.parent.left == k) {
            k.parent.left = null;
        }
        else if (k.parent != null) {
            k.parent.right = null;
        }
        return k;
    }

    public Node findLastForDeletion(Node n, int current, int height) {
        if (current == height && n != null) {
            return n;
        }
        else if (n == null) {
            return n;
        }
        else {
            Node k = findLastForDeletion(n.right, current + 1, height);
            if (k != null) {
                return k;
            }
            else {
                return findLastForDeletion(n.left, current + 1, height);
            }
        }
    }

   public int findHeightforDeletion() {
        Node l = this.root;
        int lCount = 0;
        while (l != null) {
            l = l.left;
            lCount ++;
        }
        return lCount;
    } 

我的添加功能与此相同。我只需要帮助弄清楚如何在删除之前获取最后一个节点。谢谢您的帮助！

标签： javaheapmin-heap