> For the complete documentation index, see [llms.txt](https://liuxue2010.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuxue2010.gitbook.io/data-structure-and-algorithms/sorting/heap-sort.md).

# Heap Sort

```
class Solution:
    # @param A: Given an integer array
    # @return: void
    def heapify(self, A):
        for i in range(len(A) / 2 - 1, -1, -1):
            self.shiftdown(A, i)
        # write your code here
    def shiftdown(self, A, k):
        while k < len(A):
            smallest = k
            if 2 * k + 1 < len(A) and A[2 * k + 1] < A[smallest]:
                smallest = 2 * k + 1
            if 2 * k + 2 < len(A) and A[2 * k + 2] < A[smallest]:
                smallest = 2 * k + 2
            if smallest == k:
                break
            A[k], A[smallest] = A[smallest], A[k]
            k = smallest
```