Xóa nút tùy ý từ Max/Min HBLT không phải thao tác chuẩn của Priority Queue hay HBLT. Muốn xóa nút K từ HBLT, làm theo quy tắc:
- Tách cây con gốc K khỏi cây, thay bằng meld của hai cây con của K.
- Cập nhật giá trị s trên đường từ K đến gốc, hoán đổi cây con trên đường này nếu cần để giữ tính chất HBLT.
Để cập nhật s từ K lên gốc, cần con trỏ cha cho mỗi nút. Quá trình dừng khi s không thay đổi. Các s thay đổi tạo dãy tăng dần (mỗi nút lớn hơn trước 1). Vì max s = O(log n) và s > 0, tối đa O(log n) nút được cập nhật. Mỗi nút O(1). Tổng O(log n).