<jupyter_start><jupyter_text>Heap<jupyter_code>import graphviz
import IPython
from math import inf, nan
def new_heap():
    return [nan]

def heap_push(heap, x):
    heap.append(x)
    cur = len(heap) - 1
    while x < heap[cur // 2]:
        heap[cur], heap[cur // 2] = heap[cur // 2], heap[cur]
        cur = cur // 2

def heap_top(heap):
    if len(heap) > 1:
        return heap[1]
    return None

def heapify(heap, cur):
    while 2 * cur < len(heap):
        target = 2 * cur
        if target + 1 < len(heap) and heap[target+1] < heap[target]:
            target += 1
        if heap[target] < heap[cur]:
            heap[target], heap[cur] = heap[cur], heap[target]
            cur = target
        else:
            return
    return

def heap_pop(heap):
    if len(heap) < 2:
        return
    heap[1], heap[-1] = heap[-1], heap[1]
    heap.pop()
    heapify(heap, 1)

def heap_is_empty(heap):
    return len(heap) <= 1

def make_heap(array):
    for i in range(len(array) // 2, 0, -1):
        heapify(array, i)

h = new_heap()
for i in range(10, 0, -1):
    heap_push(h, i)

print(h)
while not heap_is_empty(h):
    print(heap_top(h))
    heap_pop(h)
def heap_to_tree(heap):
    g = graphviz.Digraph()
    if not heap_is_empty(heap):
        q = [1]
        g.node(str(heap[1]))
        while len(q) > 0:
            cur = q.pop(0)
            if cur * 2 < len(heap):
                q.append(cur * 2)
                g.edge(str(heap[cur]), str(heap[cur * 2]))
            if cur * 2 + 1 < len(heap):
                q.append(cur * 2 + 1)
                g.edge(str(heap[cur]), str(heap[cur * 2 + 1]))
    return g
h = new_heap()
for i in range(5, 0, -1):
    heap_push(h, i)
    IPython.display.display(heap_to_tree(h))
    print(h)
def heap_push_display(heap, x):
    IPython.display.display(heap_to_tree(heap))
    heap.append(x)
    cur = len(heap) - 1
    while x < heap[cur // 2]:
        IPython.display.display(heap_to_tree(heap))
        print(heap)
        heap[cur], heap[cur // 2] = heap[cur // 2], heap[cur]
        cur = cur // 2
    IPython.display.display(heap_to_tree(heap))
    print(heap)

h = new_heap()
for i in range(7, 1, -1):
    heap_push(h, i)

heap_to_tree(h)
print(h)

heap_push_display(h, 1)
array = [nan] + [i for i in range(10, 0, -1)]
IPython.display.display(heap_to_tree(array))
print(array)
make_heap(array)
IPython.display.display(heap_to_tree(array))
print(array)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15349979533360622, 'fraction_numerical': 0.02251330331559558, 'mean_word_length': 2.3433652530779754, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '410777', 'license': 'BSD-2-Clause', 'n_tokens_mistral': 972, 'n_tokens_neox': 930, 'n_words': 221, 'path': 'DataStructures/Heap/Heap.ipynb', 'repo_name': 'slashvar/algolia-back-to-school', 'size': '2443'}