<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 This notebook implements an array-based version of Heapsort.
Heapsort
The function call swap(A, i, j) takes an array A and  two indexes i and j and exchanges the elements at these indexes.
Step1:  The procedure sink takes three arguments.
- A is the array representing the heap.
- k is an index into the array A.
- n is the upper bound  of the part of this array that has to be transformed into a heap.  
The array A itself might actually have more than $n+1$ elements, but for the
purpose of the method sink we restrict our attention to the subarray
A[k
Step2:  The function call heapSort(A) has the task to sort the array A and proceeds in two phases.
- In phase one our goal is to transform the array Ainto a heap that is stored in A.
In order to do so, we traverse the array A in reverse in a loop.
  The invariant of this loop is that before 
  sink is called, all trees rooted at an index greater than 
  k satisfy the heap condition.  Initially this is true because the trees that
  are rooted at indices greater than  $(n + 1) // 2 - 1$ are trivial, i.e. they only
  consist of their root node.  
In order to maintain the invariant for index k, sink is called with
  argument k,  since at this point, the tree rooted at index k satisfies
  the heap condition except possibly at the root.  It is then the job of $\texttt{sink}$ to
  establish the heap condition at index k.  If the element at the root has a
  priority that is too low, sink ensures that this element sinks down in the tree
  as far as necessary.
- In phase two we remove the elements from the heap one-by-one and insert them at the end of
  the array.
When the while-loop starts, the array A contains a heap.  Therefore,
  the smallest element is found at the root of the heap.  Since we want to sort the
  array A descendingly, we move this element to the end of the array A and in
  return move the element from the end of the arrayAto the front.
  After this exchange, the sublist A[0
Step3:  The version of heap_sort given below adds some animation.
Step4:  Testing
Step5:  The function $\texttt{testSort}(n, k)$ generates $n$ random lists of length $k$, sorts them, and checks whether the output is sorted and contains the same elements as the input.
Step6:  Next, we sort a million random integers.  It is not as fast as merge sort, but we do not need an auxiliary array and hence we don't need additional storage.
<ASSISTANT_TASK:>
Python Code:
def swap(A, i, j):
    A[i], A[j] = A[j], A[i]
Explanation: This notebook implements an array-based version of Heapsort.
Heapsort
The function call swap(A, i, j) takes an array A and  two indexes i and j and exchanges the elements at these indexes.
End of explanation
def sink(A, k, n):
    while 2 * k + 1 <= n:
        j = 2 * k + 1
        if j + 1 <= n and A[j] > A[j + 1]:
            j += 1
        if A[k] < A[j]:
            return
        swap(A, k, j)
        k = j
Explanation: The procedure sink takes three arguments.
- A is the array representing the heap.
- k is an index into the array A.
- n is the upper bound  of the part of this array that has to be transformed into a heap.  
The array A itself might actually have more than $n+1$ elements, but for the
purpose of the method sink we restrict our attention to the subarray
A[k:n]. 
When calling sink, the assumption is that A[k:n+1] should represent a heap 
that possibly has its heap condition violated at its root, i.e. at index k.  The
purpose of the procedure sink is to restore the heap condition at index k.
- We compute the index j of the left subtree below index k.
- We check whether there also is a right subtree at position j+1.
This is the case if j + 1 &lt;= n.
- If the heap condition is violated at index k, we exchange the element at  position k 
  with the child that has the higher priority, i.e. the child that is smaller. 
- Next, we check in line 9 whether the heap condition is violated at index k.
  If the heap condition is satisfied, there is nothing left to do and the procedure returns.  
Otherwise, the element at position k is swapped with
  the element at position j.  
Of course, after this swap it is possible that the heap condition is
  violated at position j.  Therefore,  k is set to j and the while-loop continues
  as long as the node at position k has at least one child, i.e. as long as 
  2 * k + 1 &lt;= n.
End of explanation
def heap_sort(A):
    n = len(A) - 1
    for k in range((n + 1) // 2 - 1, -1, -1):
        sink(A, k, n)
    while n >= 1:
        swap(A, 0, n)
        n -= 1
        sink(A, 0, n)
Explanation: The function call heapSort(A) has the task to sort the array A and proceeds in two phases.
- In phase one our goal is to transform the array Ainto a heap that is stored in A.
In order to do so, we traverse the array A in reverse in a loop.
  The invariant of this loop is that before 
  sink is called, all trees rooted at an index greater than 
  k satisfy the heap condition.  Initially this is true because the trees that
  are rooted at indices greater than  $(n + 1) // 2 - 1$ are trivial, i.e. they only
  consist of their root node.  
In order to maintain the invariant for index k, sink is called with
  argument k,  since at this point, the tree rooted at index k satisfies
  the heap condition except possibly at the root.  It is then the job of $\texttt{sink}$ to
  establish the heap condition at index k.  If the element at the root has a
  priority that is too low, sink ensures that this element sinks down in the tree
  as far as necessary.
- In phase two we remove the elements from the heap one-by-one and insert them at the end of
  the array.
When the while-loop starts, the array A contains a heap.  Therefore,
  the smallest element is found at the root of the heap.  Since we want to sort the
  array A descendingly, we move this element to the end of the array A and in
  return move the element from the end of the arrayAto the front.
  After this exchange, the sublist A[0:n-1] represents a heap, except that the
  heap condition might now be violated at the root.  Next, we decrement n, since the
  last element of the array A is already in its correct position.
  In order to reestablish the heap condition at the root, we call sink with index
  0.
End of explanation
def heap_sort(A):
    n = len(A) - 1
    for k in range((n + 1) // 2 - 1, -1, -1):
        sink(A, k, n)
    while n >= 1:
        swap(A, 0, n)
        n -= 1
        sink(A, 0, n)
Explanation: The version of heap_sort given below adds some animation.
End of explanation
import random as rnd
def isOrdered(L):
    for i in range(len(L) - 1):
        assert L[i] >= L[i+1]
from collections import Counter
def sameElements(L, S):
    assert Counter(L) == Counter(S)
Explanation: Testing
End of explanation
def testSort(n, k):
    for i in range(n):
        L = [ rnd.randrange(2*k) for x in range(k) ]
        oldL = L[:]
        heap_sort(L)
        isOrdered(L)
        sameElements(L, oldL)
        assert len(L) == len(oldL)
        print('.', end='')
    print()
    print("All tests successful!")
%%time
testSort(100, 20_000)
Explanation: The function $\texttt{testSort}(n, k)$ generates $n$ random lists of length $k$, sorts them, and checks whether the output is sorted and contains the same elements as the input.
End of explanation
%%time
k = 1000_000
L = [ rnd.randrange(2 * k) for x in range(k) ]
S = heap_sort(L)
Explanation: Next, we sort a million random integers.  It is not as fast as merge sort, but we do not need an auxiliary array and hence we don't need additional storage.
End of explanation
<END_TASK>