Heap sort

Heap sort

A bulk comparison process based on comparisons based on Binary Heap data structure. It's like a sort of choice where we start to get something low and put something small at the beginning, and we repeat the same process for the remaining elements.

What is a binary heap?

Let's first define the Complete Binary Tree. A complete binary tree is a binary tree in which all levels, except the last one, are completely completed, and all nodes are as far away as possible.

A Binary Heap is a Complete Binary tree where items are kept in a special way that the value of a parent's property is greater (or less) than the value of its two children's properties. The first is called max heap, and the last is called min-heap. A binary tree or a list can represent the bulk.

Why a Binary Heap-based arrangement?

Since Binary Heap is a Complete Binary Tree, it can be easily represented as similar members, and array-based representations apply locally. If the parent node is kept in point I, the left child can be counted in 2 * I + 1 and the right child in 2 * I + 2 (assuming the index starts at 0).

Heap Sort Algorithm for sorting in increasing order:

1. Create large quantities from input data.
2. At this point, the largest object is kept at the root of the pile. Substitute the last item of the pile, followed by reducing the pile size by 1. Finally, tie the root of the tree.
3. Repeat step 2 when the size of the pile is greater than 1.

How do you build the heap?

The Heapify process can only be applied to a node if its children's nodes are compiled. The overlap should therefore be done in low order. Let's understand with the help of an example:

Input data: 4, 10, 3, 5, 1

The numbers in parentheses represent the members of the same groupdata representation.

Using the heapify process in index 1:

Using the heapify process in index 0:

The heapify procedure calls itself recursively to build the heap in a top-down manner.