<jupyter_start><jupyter_text>heapsortAn in-place, array-based heap sort algorithm in Python. ConceptsThere are a few concepts that are involved in heap sort which bear defining. Heap TypeA heap can be either a _min_ heap or a _max_ heap. A min-heap has the lowest value at the top of the heap. Amax-heap has the highest value at the top of the heap. Heap PropertiesA heap must have the following properties: - It must be a _complete_ binary tree, meaning that the depths of any two leaf nodes must not differ by more than   one. The value of $abs(l_{i} - l_{j})$ for nodes $l_{i}$ and $l_{j}$ should only be zero or one, never greater   than one. - It must satisfy the _heap property_.   - For a max-heap, each node must be greater than or equal to the value of its children.   - For a min-heap, each node must be less than or equal to the value of each of its children.    Heap OperationsThere are a few operations which heaps usually must support: 1. Insert: insert a new element into an already valid heap. 2. Pop: remove the largest (in a max-heap) or the smallest (in a min-heap) value from a heap and repair the heap    property.    When building a heap in-place with totally unordered data, _sifting_ is another operation which works to repairthe heap property.    HeapifyingThere are two different ways to take an invalid heap and repair it into a valid heap, _sift down_ and _sift up_.Taking an unordered array and creating a heap out of it is called _heapifying_ the array. 1. **Sift Up** works by repairing the heap property upward, carrying a value upward until the heap property is    satisfied. 2. **Sift Down** works by repairing the heap property downward, carrying a value downward until the heap property    is satisfied. Sift Down HeapifyHeapify via sift-down starts at the last index in the array and works toward index zero, sifting down at each index in the array in this given order.Sift-down for a given node checks that the given node's value is $\geq$ (greater than or equal to: max-heap) or$\leq$ (less than or equal to: min-heap) its children.> **NOTE:** For reasons that are complicated, sift down amortizes to $O(n)$ time instead of what we would expect, > $O(n * log_{2}(n))$.Pseudocode:```for i in reversed(range(len(data)):    sift_down(data, i)```  Sift Up HeapifyHeapify via sift-up starts at the first index in the array and sifts up for each following index in the array.Sift-up for a given node checks that the given node's value is $\leq$ (less than or equal to: max-heap) or $\geq$(greater than or equal to: min-heap) the value of its parent. Sift-up climbs up the heap, repairing the heap aslong as the heap property isn't satisfied.Pseudocode:```for i in range(1, len(data)):    sift_up(data, i)``` ImplementationA full heap-sort implementation, based on sift-down as described above, will work like so: 1. **Heapify** the array into a max-heap.    - Iterate from the last index in the array to the first index in the array, calling sift-down on each index. 2. **Sort** the array by popping elements out of the heap.    1. Set an `end` index to the last index in the array.    2. Swap the first element in the heap (the largest value) with the element at `end`.    3. Sift down index zero, correcting the heap property, and stop sifting down before hitting `end`.    4. Decrement `end` and return to step 2.    In a max-heap, the largest value will always be at the head of the heap. Thus, by swapping it with the end of thearray, this will place the largest element at the last index, the second-largest element at the penultimate index,and so on and so forth, resulting in a sorted array.<jupyter_code>import unittest


def heap_parent(index):
    """Fetch the parent index of the node at the given index."""
    return int((index - 1) / 2)


def heap_left_child(index):
    """Fetch the left child index of the node at the given index."""
    return (index * 2) + 1


def heap_right_child(index):
    """Fetch the right child index of the node at the given index."""
    return (index * 2) + 2


def heapsort(data):
    """Sort an array of comparable data in-place using a heap-sort algorithm."""
    # create heap property
    heapify(data)
    
    # start from the last element
    end = len(data) - 1
    
    # work until the second element (index 1)
    while end > 0:
        # swap the end element with the first element (the end element is the greatest element in the range)
        data[end], data[0] = data[0], data[end]
        # restrict our search space to not include the last element (which is "removed" from the heap)
        end -= 1
        # the head of the heap is likely in violation of the heap property, so sift down within the window
        heap_sift_down(data, 0, end)
    
    return data


def heapify(data):
    """
    Creates a max heap out of a list in-place.
    """
    # start sifting down from the final parent in the list
    last = len(data) - 1
    index = heap_parent(last)
    
    while index >= 0:
        heap_sift_down(data, index, last)
        index -= 1
    
    return data


def heap_sift_down(data, start, end=None):
    """
    Sifts a max heap down in place.
    
    Given a start index, this will traverse down the heap, creating/fixing the heap property for itself and its
    child nodes.
    
    Args:
        data: list of comparable elements
        start: the index within data to sift down from.
        end: the last index to sift within, any elements after this index will not be sifted.
    """    
    if end is None:
        end = len(data) - 1
    
    root = start
    
    while heap_left_child(root) <= end:
        left, right, swap = heap_left_child(root), heap_right_child(root), root
        
        if data[swap] < data[left]:
            swap = left
        
        # for some reason, right always wins here
        if right <= end and data[swap] < data[right]:
            swap = right
            
        if swap == root:
            return
        else:
            data[root], data[swap] = data[swap], data[root]
            root = swap
            
    return data


class HeapSortTestCase(unittest.TestCase):
    """Heap sort tests."""
    
    def test_sift_down_limitless(self):
        """Test sifting down without any end bound."""
        # sifts here (note: the right child is always preferred in our example above)
        #   - start                (0, 1, 2, 3, 4, 5)
        #   - swap indices 0 and 2 (2, 1, 0, 3, 4, 5)
        #   - swap indices 2 and 5 (2, 1, 5, 3, 4, 0)
        self.assertEqual([2, 1, 5, 3, 4, 0], heap_sift_down([0, 1, 2, 3, 4, 5], 0))
    
    def test_sift_down_limited(self):
        """Test sifting down with a specified end bound."""
        # sifts here (note: the right child is always preferred in our example above)
        #   - start                (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...)
        #   - swap indices 0 and 2 (2, 1, 0, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...)
        #   - swap indices 2 and 6 (2, 1, 6, 3, 4, 5, 0, 7, 8, 9, 10, 11, ...)
        self.assertEqual(
            [2, 1, 6, 3, 4, 5, 0, 7, 8, 9, 10, 11, 12, 13, 14, 15], 
            heap_sift_down(list(range(16)), 0, 10),
        )

    def test_sift_down_start(self):
        """Test sifting down with a different start index."""
        # sifts here (note: the right child is always preferred in our example above)
        #   - start (index 3)      (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...)
        #   - swap indices 3 and 8 (0, 1, 2, 8, 4, 5, 6, 7, 3, 9, 10, 11, ...)
        self.assertEqual(
            [0, 1, 2, 8, 4, 5, 6, 7, 3, 9, 10, 11, 12, 13, 14, 15],
            heap_sift_down(list(range(16)), 3),
        )
        
    
    @unittest.skip
    def test_sift_up(self):
        self.fail()
    
    def test_heapify(self):
        """Test that heapifying an array works."""
        data = heapify([2, 5, 3, 17, 8, 12])
        
        for start in reversed(range(len(data))):
            current = start
            # walk upward evaluating the heap property
            while current > 0:
                parent = heap_parent(current)
                self.assertGreaterEqual(data[parent], data[current],
                    "Heap property invalid at {:d} (parent {:d})".format(current, parent))
                
                current = parent
                
        # prove by implementation details
        # heapify(2, 5, 3, 17, 8, 12)
        #     heap_sift_down(data, 3)
        #         start: [2, 5, 3, 17, 8, 12]
        #         
        self.assertEqual(
            [17, 8, 12, 5, 2, 3], 
            data
        )

    def test_heapsort(self):
        """Tests that heapsort sorts a list into ascending order."""
        self.assertEqual([0, 1, 2, 3, 4, 5], heapsort(list(reversed(range(6)))))
        
    def test_heap_left_child(self):
        """Tests fetching the left child index of a given node."""
        self.assertEqual(1, heap_left_child(0))
        self.assertEqual(3, heap_left_child(1))
        
    def test_heap_right_child(self):
        """Tests fetching the right child index of a given node."""
        self.assertEqual(2, heap_right_child(0))
        self.assertEqual(4, heap_right_child(1))
        
    def test_heap_parent(self):
        """Tests fetching the parent index of a given node."""
        self.assertEqual(0, heap_parent(0))
        self.assertEqual(2, heap_parent(5))
        self.assertEqual(2, heap_parent(6))

unittest.main(argv=[''], verbosity=1, exit=False)<jupyter_output>.........
----------------------------------------------------------------------
Ran 9 tests in 0.006s

OK
{'fraction_non_alphanumeric': 0.10256943722043067, 'fraction_numerical': 0.02652657859149069, 'mean_word_length': 2.401981599433829, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '294272', 'license': 'Apache-2.0', 'n_tokens_mistral': 3048, 'n_tokens_neox': 2787, 'n_words': 1289, 'path': 'notebooks/python/heapsort.ipynb', 'repo_name': 'naftulikay/joop', 'size': '9613'}