<commit_before># Copyright © 2014 <NAME>
# heap sort, from CLR pp. 142-
# zero-based indexing, top is min

from random import randrange

def exchange(a, i, j):
    tmp = a[i]
    a[i] = a[j]
    a[j] = tmp

def left(i):
    return 2 * i + 1

def right(i):
    return 2 * i + 2

def parent(i):
    # XXX (i - 1) // 2 doesn't work, because i = 0
    return (i + 1) // 2 - 1

def checkheap(a, na, i):
    if i < na // 2 - 1:
        assert a[i] >= a[left(i)] and a[i] >= a[right(i)]
        checkheap(a, na, left(i))
        checkheap(a, na, right(i))

def downheap(a, na, i):
    while (right(i) < na):
        xl = a[i] < a[left(i)]
        xr = a[i] < a[right(i)]
        if not xl and not xr:
            break
        xo = a[left(i)] >= a[right(i)]
        if xl and xo:
            exchange(a, i, left(i))
            i = left(i)
            continue<commit_msg>fixed spec bug in heapsort<commit_after># Copyright © 2014 <NAME>
# heap sort, from CLR pp. 142-
# zero-based indexing, top is min

from random import randrange

def exchange(a, i, j):
    tmp = a[i]
    a[i] = a[j]
    a[j] = tmp

def left(i):
    return 2 * i + 1

def right(i):
    return 2 * i + 2

def parent(i):
    return (i - 1) // 2

def checkheap(a, na, i):
    if i < na // 2 - 1:
        assert a[i] >= a[left(i)] and a[i] >= a[right(i)]
        checkheap(a, na, left(i))
        checkheap(a, na, right(i))

def downheap(a, na, i):
    while (right(i) < na):
        xl = a[i] < a[left(i)]
        xr = a[i] < a[right(i)]
        if not xl and not xr:
            break
        xo = a[left(i)] >= a[right(i)]
        if xl and xo:
            exchange(a, i, left(i))
            i = left(i)
            continue
{'fraction_non_alphanumeric': 0.16587677725118483, 'fraction_numerical': 0.02014218009478673, 'mean_word_length': 1.829145728643216, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 11, '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}}
{'dir': 'git-commits-cleaned', 'id': '5845998', 'n_tokens_mistral': 711, 'n_tokens_neox': 671, 'n_words': 217}