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

# Heap Sort

## What is a heap?

A heap is a tree that has the "heap" property. There can be either max heaps or min heaps. A max heap has the property that for every parent node, it's key is greater than or equal to the key of its child nodes. In other words, in a max heap, the biggest number is at the top.

![Max Heap](https://res.cloudinary.com/briezh/image/upload/v1519762182/Max-Heap_eir7zo.png)

A min heap is similar to a max heap, except that the parent's key is less than or equal to the child's key. Therefore in a min heap, the smallest number is at the top (or root) of the tree.

## What is heapsort?

Heapsort uses a heap data structure in order to perform a sort. It's an in-place comparison sort. The code implementation uses 3 functions: Heapsort, BuildHeap, and Heapify. Heapsort is the main/entry function, BuildHeap forms your initial heap, and Heapify is to make a non-heap tree into a heap. An important thing to recognize is that an array can be a representation of a tree. Imagine arr\[0] as the root of the tree and arr\[1] and arr\[2] as the left and right nodes of the root. Then arr\[3] and arr\[4] would be the left and right nodes of arr\[1], and so on. For example, take the max heap pictured above. In an array representation that would look like:

```
arr = [100, 19, 36, 17, 3, 25, 1, 2, 7]
```

Thus, for any given index `i`, its children are:

* left: `2*i + 1`
* right: `2*i + 2`

### Pseudocode

The pseudocode for the algorithm goes like this: 1. Using the given array, build a heap using recursive insertion 2. Iterate to extract the max element in the heap and then reheapify the heap 3. Extracted elements form a sorted subsequence

```
Heapsort(Arr)
    BuildHeap(Arr)
    for i in range Arr size down to 1
        swap(Arr[1], Arr[i])
        NewSize = reduce size by one
        Heapify(Arr, NewSize, 1)

BuildHeap(Arr)
    n = Arr size
    for i in floor(n/2) down to 0
        Heapify(Arr, n, i AKA the RootIndex)

Heapify(Arr, i, size)
    max = i
    left = 2i
    right = 2i+1

    if (left <= size) and (Arr[left] > Arr[max])
        max = left

    if (right<=size) and (Arr[right] > Arr[max])
        max = right

    if (max != i)
        swap(Arr[i], Arr[max])
        Heapify(Arr, max)
```

### Code in Python

For working code in Python, [visit this repl](https://repl.it/@brandiw/HeapSort).

```
def heap_sort(list):
  # For ease, let's make a variable for the size of the array
  size = len(list)

  # Build inital heap structure
  build_heap(list, size)

  # Loop from length down to 2 to heapify
  for i in range(size - 1, 0, -1):
    #swap first and "last"
    list[0], list[i] = list[i], list[0]

    # Call heapify on reduced list size
    heapify(list, i, 0)

  return list

# Convert array/list to a heap  
def build_heap(list, size):
  for i in range(size // 2, -1, -1):
    heapify(list, size, i)

# Make our tree into a max heap
def heapify(sublist, size, root_index):
  largest = root_index
  left = 2*root_index + 1
  right = 2*root_index + 2

  if(left < size and sublist[left] > sublist[largest]):
    largest = left
  if(right < size and sublist[right] > sublist[largest]):
    largest = right

  if(root_index != largest):
    sublist[largest], sublist[root_index] = sublist[root_index], sublist[largest]
    heapify(sublist, size, largest)


# Test Data
print(heap_sort([8, 2, 1, 4, 6, 5, 7, 3, 22, 1, 19, 3, 33, 7, -3, 111, 21, -4, 0, 99, 89]))
```

## References

* [Pseudocode Source](http://www.algorithmist.com/index.php/Heap_sort)
* [Coding Geek Implementation/Explanation](https://www.codingeek.com/algorithms/heap-sort-algorithm-explanation-and-implementation/)
* [Example Code](https://repl.it/@brandiw/HeapSort)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://romebell.gitbook.io/seirfx-621/data-structures-and-algorithms/cs-heap-sort.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.