{
    "content": [
        {
            "type": "text",
            "text": "# _heapq (pydoc)\n\n**Summary:** heapq - Heap queue algorithm (a.k.a. priority queue).\n\n## Section Outline\n\n- **NAME** (2 lines)\n- **DESCRIPTION** (8 lines) — 2 subsections\n  - heappush (2 lines)\n  - heapify (15 lines)\n- **FUNCTIONS** (1 lines) — 5 subsections\n  - heapify (2 lines)\n  - heappop (2 lines)\n  - heappush (2 lines)\n  - heappushpop (5 lines)\n  - heapreplace (10 lines)\n- **DATA** (2 lines)\n- **FILE** (3 lines)\n\n## Full Content\n\n### NAME\n\nheapq - Heap queue algorithm (a.k.a. priority queue).\n\n### DESCRIPTION\n\nHeaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\nall k, counting elements from 0.  For the sake of comparison,\nnon-existing elements are considered to be infinite.  The interesting\nproperty of a heap is that a[0] is always its smallest element.\n\nUsage:\n\nheap = []            # creates an empty heap\n\n#### heappush\n\nitem = heappop(heap) # pops the smallest item from the heap\nitem = heap[0]       # smallest item on the heap without popping it\n\n#### heapify\n\nitem = heapreplace(heap, item) # pops and returns smallest item, and adds\n# new item; the heap size is unchanged\n\nOur API differs from textbook heap algorithms as follows:\n\n- We use 0-based indexing.  This makes the relationship between the\nindex for a node and the indexes for its children slightly less\nobvious, but is more suitable since Python uses 0-based indexing.\n\n- Our heappop() method returns the smallest item, not the largest.\n\nThese two make it possible to view the heap as a regular Python list\nwithout surprises: heap[0] is the smallest item, and heap.sort()\nmaintains the heap invariant!\n\n### FUNCTIONS\n\n#### heapify\n\nTransform list into a heap, in-place, in O(len(heap)) time.\n\n#### heappop\n\nPop the smallest item off the heap, maintaining the heap invariant.\n\n#### heappush\n\nPush item onto heap, maintaining the heap invariant.\n\n#### heappushpop\n\nPush item on the heap, then pop and return the smallest item from the heap.\n\nThe combined action runs more efficiently than heappush() followed by\na separate call to heappop().\n\n#### heapreplace\n\nPop and return the current smallest value, and add the new item.\n\nThis is more efficient than heappop() followed by heappush(), and can be\nmore appropriate when using a fixed-size heap.  Note that the value\nreturned may be larger than item!  That constrains reasonable uses of\nthis routine unless written as part of a conditional replacement:\n\nif item > heap[0]:\nitem = heapreplace(heap, item)\n\n### DATA\n\nabout = 'Heap queues\\n\\n[explanation by François Pinard]\\n\\nH... t...\n\n### FILE\n\n(built-in)\n\n"
        }
    ],
    "structuredContent": {
        "command": "_heapq",
        "section": "",
        "mode": "pydoc",
        "summary": "heapq - Heap queue algorithm (a.k.a. priority queue).",
        "synopsis": null,
        "tldr_summary": null,
        "tldr_examples": [],
        "tldr_source": null,
        "flags": [],
        "examples": [],
        "see_also": [],
        "section_outline": [
            {
                "name": "NAME",
                "lines": 2,
                "subsections": []
            },
            {
                "name": "DESCRIPTION",
                "lines": 8,
                "subsections": [
                    {
                        "name": "heappush",
                        "lines": 2
                    },
                    {
                        "name": "heapify",
                        "lines": 15
                    }
                ]
            },
            {
                "name": "FUNCTIONS",
                "lines": 1,
                "subsections": [
                    {
                        "name": "heapify",
                        "lines": 2
                    },
                    {
                        "name": "heappop",
                        "lines": 2
                    },
                    {
                        "name": "heappush",
                        "lines": 2
                    },
                    {
                        "name": "heappushpop",
                        "lines": 5
                    },
                    {
                        "name": "heapreplace",
                        "lines": 10
                    }
                ]
            },
            {
                "name": "DATA",
                "lines": 2,
                "subsections": []
            },
            {
                "name": "FILE",
                "lines": 3,
                "subsections": []
            }
        ]
    }
}