{
    "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- **MODULE REFERENCE** (8 lines)\n- **DESCRIPTION** (8 lines) — 2 subsections\n  - heappush (2 lines)\n  - heapify (15 lines)\n- **FUNCTIONS** (1 lines) — 8 subsections\n  - heapify (2 lines)\n  - heappop (2 lines)\n  - heappush (2 lines)\n  - heappushpop (5 lines)\n  - heapreplace (10 lines)\n  - merge (15 lines)\n  - nlargest (4 lines)\n  - nsmallest (4 lines)\n- **DATA** (3 lines)\n- **FILE** (3 lines)\n\n## Full Content\n\n### NAME\n\nheapq - Heap queue algorithm (a.k.a. priority queue).\n\n### MODULE REFERENCE\n\nhttps://docs.python.org/3.10/library/heapq.html\n\nThe following documentation is automatically generated from the Python\nsource files.  It may be incomplete, incorrect or include features that\nare considered implementation detail and may vary between Python\nimplementations.  When in doubt, consult the module reference at the\nlocation listed above.\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#### merge\n\nMerge multiple sorted inputs into a single sorted output.\n\nSimilar to sorted(itertools.chain(*iterables)) but returns a generator,\ndoes not pull the data into memory all at once, and assumes that each of\nthe input streams is already sorted (smallest to largest).\n\n>>> list(merge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25]))\n[0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25]\n\nIf *key* is not None, applies a key function to each element to determine\nits sort order.\n\n>>> list(merge(['dog', 'horse'], ['cat', 'fish', 'kangaroo'], key=len))\n['dog', 'cat', 'fish', 'horse', 'kangaroo']\n\n#### nlargest\n\nFind the n largest elements in a dataset.\n\nEquivalent to:  sorted(iterable, key=key, reverse=True)[:n]\n\n#### nsmallest\n\nFind the n smallest elements in a dataset.\n\nEquivalent to:  sorted(iterable, key=key)[:n]\n\n### DATA\n\nabout = 'Heap queues\\n\\n[explanation by François Pinard]\\n\\nH... t...\nall = ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', '...\n\n### FILE\n\n/usr/lib/python3.10/heapq.py\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": "MODULE REFERENCE",
                "lines": 8,
                "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": "merge",
                        "lines": 15
                    },
                    {
                        "name": "nlargest",
                        "lines": 4
                    },
                    {
                        "name": "nsmallest",
                        "lines": 4
                    }
                ]
            },
            {
                "name": "DATA",
                "lines": 3,
                "subsections": []
            },
            {
                "name": "FILE",
                "lines": 3,
                "subsections": []
            }
        ]
    }
}