Heap Sort a Sorting Algorithm

Heap Sort a Sorting Algorithm

Heap Sort
Heap Sort

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort a list of numbers in ascending or descending order.

A binary heap is a complete binary tree (that is, a tree in which every level is completely filled except possibly the last level, and the last level is filled from left to right) in which the value of each node is greater than or equal to the values of its children. In a max-heap, the value of each node is greater than or equal to the values of its children, while in a min-heap, the value of each node is less than or equal to the values of its children.

To sort a list using heap sort:

  1. Build a max-heap or min-heap from the list.
  2. Swap the root element (which is the maximum or minimum element in a heap) with the last element in the heap.
  3. Remove the last element from the heap and re-heapify the remaining elements to maintain the heap property.
  4. Repeat steps 2 and 3 until the heap is empty.

CT The time complexity of heap sort is O(n log n), making it more efficient than bubble sort, insertion sort, and selection sort, but slightly less efficient than merge sort and quick sort. However, heap sort has the advantage of being a stable sort, meaning that the order of elements with equal values is preserved.

 

function heap_sort(A)
    build_max_heap(A)
    for i = length(A) down to 2
        swap(A[1], A[i])
        heap_size = heap_size - 1
        max_heapify(A, 1)
    end for
end function

function build_max_heap(A)
    heap_size = length(A)
    for i = floor(length(A) / 2) down to 1
        max_heapify(A, i)
    end for
end function

function max_heapify(A, i)
    left = left(i)
    right = right(i)
    if left <= heap_size and A[left] > A[i]
        largest = left
    else
        largest = i
    end if
    if right <= heap_size and A[right] > A[largest]
        largest = right
    end if
    if largest != i
        swap(A[i], A[largest])
        max_heapify(A, largest)
    end if
end function

Heap sort in different languagesĀ 

C++

#include <iostream>
#include <vector>

void heapify(std::vector<int> &nums, int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2*i + 1; // left = 2*i + 1
    int right = 2*i + 2; // right = 2*i + 2

    // If left child is larger than root
    if (left < n && nums[left] > nums[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && nums[right] > nums[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        std::swap(nums[i], nums[largest]);

        // Recursively heapify the affected sub-tree
        heapify(nums, n, largest);
    }
}

void heap_sort(std::vector<int> &nums) {
    int n = nums.size();

    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(nums, n, i);

    // One by one extract an element from heap
    for (int i=n-1; i>=0; i--) {
        // Move current root to end
        std::swap(nums[0], nums[i]);

        // call max heapify on the reduced heap
        heapify(nums, i, 0);
    }
}

int main() {
    std::vector<int> nums = {4, 10, 3, 5, 1};
    heap_sort(nums);
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

Python

def heapify(nums, n, i):
    largest = i # Initialize largest as root
    left = 2*i + 1 # left = 2*i + 1
    right = 2*i + 2 # right = 2*i + 2
    # If left child is larger than root
    if left < n and nums[left] > nums[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and nums[right] > nums[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        nums[i], nums[largest] = nums[largest], nums[i] # swap
        # Recursively heapify the affected sub-tree
        heapify(nums, n, largest)

def heap_sort(nums):
    n = len(nums)
    # Build heap (rearrange array)
    for i in range(n//2 - 1, -1, -1):
        heapify(nums, n, i)
    # One by one extract an element from heap
    for i in range(n-1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i] # Move current root to end
        heapify(nums, i, 0)
        
nums = [4, 10, 3, 5, 1]
heap_sort(nums)
print(nums)

Java

import java.util.Arrays;

public class HeapSort {
    public static void heapify(int[] nums, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2*i + 1; // left = 2*i + 1
        int right = 2*i + 2; // right = 2*i + 2

        // If left child is larger than root
        if (left < n && nums[left] > nums[largest])
            largest = left;

        // If right child is larger than largest so far
        if (right < n && nums[right] > nums[largest])
            largest = right;

        // If largest is not root
        if (largest != i) {
            // swap
            int temp = nums[i];
            nums[i] = nums[largest];
            nums[largest] = temp;

            // Recursively heapify the affected sub-tree
            heapify(nums, n, largest);
        }
    }

    public static void heapSort(int[] nums) {
        int n = nums.length;

        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(nums, n, i);

        // One by one extract an element from heap
        for (int i=n-1; i>=0; i--) {
            // Move current root to end
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;

            // call max heapify on the reduced heap
            heapify(nums, i, 0);
        }
    }

    public static void main(String[] args) {
        int[] nums = {4, 10, 3, 5, 1};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

JavaScript

function heapify(nums, n, i) {
    let largest = i;  // Initialize largest as root
    let left = 2*i + 1;  // left = 2*i + 1
    let right = 2*i + 2;  // right = 2*i + 2
    // If left child is larger than root
    if (left < n && nums[left] > nums[largest]) {
        largest = left;
    }
    // If right child is larger than largest so far
    if (right < n && nums[right] > nums[largest]) {
        largest = right;
    }
    // If largest is not root
    if (largest !== i) {
        [nums[i], nums[largest]] = [nums[largest], nums[i]];  // swap
        // Recursively heapify the affected sub-tree
        heapify(nums, n, largest);
    }
}

function heapSort(nums) {
    let n = nums.length;
    // Build heap (rearrange array)
    for (let i = Math.floor(n/2) - 1; i >= 0; i--) {
        heapify(nums, n, i);
    }
    // One by one extract an element from heap
    for (let i = n - 1; i >= 0; i--) {
        [nums[0], nums[i]] = [nums[i], nums[0]];  // Move current root to end
        heapify(nums, i, 0);
    }
}

let nums = [4, 10, 3, 5, 1];
heapSort(nums);
console.log(nums);

PHP

function heapify(&$nums, $n, $i) {
    $largest = $i;  // Initialize largest as root
    $left = 2*$i + 1;  // left = 2*i + 1
    $right = 2*$i + 2;  // right = 2*i + 2
    // If left child is larger than root
    if ($left < $n && $nums[$left] > $nums[$largest]) {
        $largest = $left;
    }
    // If right child is larger than largest so far
    if ($right < $n && $nums[$right] > $nums[$largest]) {
        $largest = $right;
    }
    // If largest is not root
    if ($largest != $i) {
        list($nums[$i], $nums[$largest]) = array($nums[$largest], $nums[$i]);  // swap
        // Recursively heapify the affected sub-tree
        heapify($nums, $n, $largest);
    }
}

function heapSort(&$nums) {
    $n = count($nums);
    // Build heap (rearrange array)
    for ($i = floor($n/2) - 1; $i >= 0; $i--) {
        heapify($nums, $n, $i);
    }
    // One by one extract an element from heap
    for ($i = $n - 1; $i >= 0; $i--) {
        list($nums[0], $nums[$i]) = array($nums[$i], $nums[0]);  // Move current root to end
        heapify($nums, $i, 0);
    }
}

$nums = array(4, 10, 3, 5, 1);
heapSort($nums);
print_r($nums);


Heap sort Explanation

In this example, heapSort takes a single argument, nums, which is an array of integers that will be sorted. The function first calls heapify to build the initial heap.

heapify takes three arguments: the array to be heapified, the size of the array, and the current index.

After the heap is built, the function then repeatedly extracts the maximum element from the heap and places it at the end of the array, reducing the size of the heap by one.

Each time an element is extracted heapify is called again to maintain the heap property.

The standard JavaScript arrays are zero-indexed, so the left and right children of a node at index i are at indexes 2i + 1 and 2i + 2, respectively.

Bubble Sort Algorithm

Insertion sort: a Sorting Algorithm

Selection sort Algorithm

Quick Sort Algorithms

Merge Sort Algorithm

List of Sorting Algorithms

https://messagehimessage.com

Related Posts

This Post Has One Comment

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.