HomeOur TeamContact
Sorting
Heap Sort
Nisar
January 31, 2022
1 min

# .css-10kjd3a{box-sizing:border-box;margin:0;min-width:0;display:block;color:var(--theme-ui-colors-heading,#2d3748);font-weight:900;-webkit-text-decoration:none;text-decoration:none;margin-bottom:1rem;font-size:1.875rem;position:relative;}@media screen and (min-width:640px){.css-10kjd3a{font-size:2.25rem;}}@media screen and (min-width:1024px){.css-10kjd3a{font-size:3rem;}}Heap Sort

Heap is a special tree-based data structure. The Heap Sort is a comparison-based sorting method based on the Binary Heap data structure. Similar to Selection Sort, In this method, we move the minimum element to the beginning and everything else in ascending order. We repeat the procedure with each element.

The complexity of Space and Time

Best: O(nlog(n)) time | O(1) space

Average: O(nlog(n)) time | O(1) space

Worst: O(nlog(n)) time | O(1) space

n is the length of the input array.

Input

`[8, 5, 1, 9, 5, 6, 2]`

Output

`[1, 2, 5, 5, 6, 8, 9]`

Hint

In position, create two subarrays out of the input array. The second subarray must be sorted at all times and begin with a length of 0., The first subarray is transformed into a maximum (or minimum) heap and must always satisfy the heap property.

Pseudo Code

```DEFINE FUNCTION heapSort(array):
buildMaxHeap(array)
FOR endIdx IN reversed(range(1, len(array))):
swap(0, endIdx, array)
siftDown(0, endIdx - 1, array)
RETURN array

DEFINE FUNCTION buildMaxHeap(array):
SET firstParentIdx TO (len(array) - 2) // 2
FOR currentIdx IN reversed(range(firstParentIdx + 1)):
siftDown(currentIdx, len(array) - 1, array)

DEFINE FUNCTION siftDown(currentIdx, endIdx, heap):
SET childOneIdx TO currentIdx * 2 + 1
WHILE childOneIdx <= endIdx:
SET childTwoIdx TO currentIdx * 2 + 2 IF currentIdx * 2 + 2 <= endIdx else -1
IF childTwoIdx > -1 and heap[childTwoIdx] > heap[childOneIdx]:
SET idxToSwap TO childTwoIdx
ELSE:
SET idxToSwap TO childOneIdx
IF heap[idxToSwap] > heap[currentIdx]:
swap(currentIdx, idxToSwap, heap)
SET currentIdx TO idxToSwap
SET childOneIdx TO currentIdx * 2 + 1
ELSE:
RETURN

DEFINE FUNCTION swap(i, j, array):
SET array[i], array[j] TO array[j], array[i]
```

Solution in Typescript

```function heapSort(array: number[]) {
buildMaxHeap(array);
for (let endIdx = array.length - 1; endIdx > 0; endIdx--) {
swap(0, endIdx, array);
siftDown(0, endIdx - 1, array);
}
return array;
}

function buildMaxHeap(array: number[]) {
const firstParentIdx = Math.floor((array.length - 2) / 2);
for (let currentIdx = firstParentIdx; currentIdx >= 0; currentIdx--) {
siftDown(currentIdx, array.length - 1, array);
}
}

function siftDown(currentIdx: number, endIdx: number, heap: number[]) {
let childOneIdx = currentIdx * 2 + 1;
while (childOneIdx <= endIdx) {
const childTwoIdx = currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;
let idxToSwap;
if (childTwoIdx !== -1 && heap[childTwoIdx] > heap[childOneIdx]) {
idxToSwap = childTwoIdx;
} else {
idxToSwap = childOneIdx;
}
if (heap[idxToSwap] > heap[currentIdx]) {
swap(currentIdx, idxToSwap, heap);
currentIdx = idxToSwap;
childOneIdx = currentIdx * 2 + 1;
} else {
return;
}
}
}

function swap(i: number, j: number, array: number[]) {
const temp = array[j];
array[j] = array[i];
array[i] = temp;
}

mocha.setup("bdd");
describe("Heap Sort", () => {
it("Test Case #1", function () {
const input = [8, 5, 1, 9, 5, 6, 2];
chai.expect(heapSort(input)).to.deep.equal([1, 2, 5, 5, 6, 8, 9]);
});

it("Test Case #2", function () {
const input =[5, 3, 1, 2, 4];
chai.expect(heapSort(input)).to.deep.equal([1,2,3,4,5]);
});
});

mocha.run();
```

Demo

https://codepen.io/evalteam/pen/PoOoMME

Previous Article
Quick Sort

Quick Sort
January 30, 2022
1 min