Data Structures

Binary Heap With Decrease-Key

Difficulty

Asked at Citadel Securities

Theory: Data Structures You Implement, Not Import

Read the problem, hints and solution here. The editor needs a bigger screen: open this page on a laptop to write and run your code.

Available in C++ and Python. You are solving it in Python. Switch to C++

This problem is only available to subscribers.

Language:

C++23 Python 3.12

run_indexed_heap

import random
from collections.abc import Sequence
from typing import Any


class IndexedMinHeap:
    """..."""

    def __init__(self) -> None:
        # ...
        pass

    def insert(self, key: int, priority: int) -> bool:
        """..."""
        # ...
        return False

    def extract_min(self) -> tuple[int, int] | None:
        """..."""
        # ...
        return None

    def decrease_key(self, key: int, new_priority: int) -> bool:
        """..."""
        # ...
        return False

    def size(self) -> int:
        # ...
        return 0


# ...
# ...
def run_indexed_heap(ops: list[tuple[Any, ...]]) -> list[bool | int | tuple[int, int] | None]:
    h = IndexedMinHeap()
    out = []
    for op in ops:
        name = op[0]
        if name == "insert":
            out.append(h.insert(op[1], op[2]))
        elif name == "extract_min":
            out.append(h.extract_min())
        elif name == "decrease_key":
            out.append(h.decrease_key(op[1], op[2]))
        elif name == "size":
            out.append(h.size())
    return out


# ...
# ...
def checksum(values: Sequence[Any]) -> int:
    h = 0
    for v in values:
        if v is None:
            x = -1
        elif isinstance(v, bool):
            x = 1 if v else 0
        elif isinstance(v, (tuple, list)):
            x = checksum(v)
        elif isinstance(v, (bytes, bytearray)):
            x = checksum(list(v)) + len(v)
        else:
            x = v
        h = (h * 1000003 + x + 2) % 1000000007
    return h

Unlock to runUpgrade

Unlock the problem to run it against the tests.

Next in Quant Dev 50LFU Cache VariantData Structures

Binary Heap With Decrease-Key

xxxxxxxx

xxxxxxxxxxx