Iterative Heap Sort
Iterative Heap Sort is a sorting algorithm that uses a heap data structure to sort an array of elements. It is an iterative version of Heap Sort, which is a recursive algorithm.
The basic idea behind Heap Sort is to convert the array into a heap data structure, where the largest element is at the root of the heap. Then, we swap the root element with the last element of the heap, and repeat the process on the remaining heap, excluding the last element, until the entire array is sorted.
In Iterative Heap Sort, we use a loop instead of recursion to build the heap and sort the array. The algorithm first builds a max heap by iterating from the middle of the array to the beginning, and calling a function that maintains the heap property by swapping elements if necessary. Once the heap is built, the algorithm swaps the root element with the last element of the heap and decreases the heap size. Then, it repeats the heapify function on the remaining heap, excluding the last element, until the entire array is sorted.
The time complexity of Iterative Heap Sort is O(n log n) in the worst case, where n is the number of elements in the array. The space complexity is O(1), as the algorithm sorts the array in-place, without using any additional memory. However, Heap Sort and Iterative Heap Sort are not stable sorting algorithms, as they may change the order of equal elements in the array.
Here given code implementation process.
//C Program
//Iterative Heap Sort
#include <stdio.h>
//Swap two element in array
void swap(int arr[],int first,int second)
{
int auxiliary=arr[first];
arr[first]=arr[second];
arr[second]=auxiliary;
}
int compare(int arr[],int left,int right,int root,int size)
{
int location = -1;
if(left < size && arr[left] > arr[root] )
{
if(right < size && arr[right] > arr[left])
{
swap(arr,right,root);
location = right;
}
else
{
swap(arr,left,root);
location = left;
}
}
else if(right < size && arr[right] > arr[root])
{
swap(arr,right,root);
location = right;
}
return location;
}
//Perform the operation of heap sort
void heap(int arr[],int size,int root)
{
int left,right;
while(root!=-1)
{
left = 2*root+1;
right = 2*root+2;
root = compare(arr, left, right, root, size);
}
}
//Sort array element using heap sort
void heap_sort(int arr[],int size)
{
for (int i = (size/2)-1; i >= 0; i--)
{
heap(arr, size, i);
}
for (int i = size-1; i >= 0; i--)
{
swap(arr, 0, i);
heap(arr, i, 0);
}
}
void print_data(int arr[],int size)
{
for(int i = 0; i < size; i++)
{
printf(" %d",arr[i] );
}
printf("\n");
}
int main()
{
//Collection of unordered sorted array
int arr[] = {6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12 ,5};
//Get the size of array
int size = sizeof(arr)/sizeof(arr[0]);
printf(" Before Sort\n");
print_data(arr,size);
heap_sort(arr,size);
printf(" After Sort\n");
print_data(arr,size);
return 0;
}
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21
/*
C++ Program
Iterative Heap Sort
*/
#include<iostream>
using namespace std;
class MyHeap {
public:
//Swap two element in array
void swap(int arr[], int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
int compare(int arr[], int left, int right, int root, int size) {
int location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
this->swap(arr, right, root);
location = right;
} else {
this->swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
this->swap(arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
void heap(int arr[], int size, int root) {
int left, right;
while (root != -1) {
left = 2 *root + 1;
right = 2 *root + 2;
root = this->compare(arr, left, right, root, size);
}
}
//Sort array element using heap sort
void heap_sort(int arr[], int size) {
for (int i = (size / 2) - 1; i >= 0; i--) {
this->heap(arr, size, i);
}
for (int i = size - 1; i >= 0; i--) {
this->swap(arr, 0, i);
this->heap(arr, i, 0);
}
}
void print_data(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
cout << "\n";
}
};
int main() {
MyHeap obj = MyHeap();
int arr[] = {
6,
8,
2,
2,
7,
1,
3,
8,
21,
11,
12,
5
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
cout << " Before Sort\n";
obj.print_data(arr, size);
obj.heap_sort(arr, size);
cout << "\n After Sort\n";
obj.print_data(arr, size);
return 0;
}
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21
/*
Java Program
Iterative Heap Sort
*/
public class MyHeap {
//Swap two element in array
public void swap(int []arr,int first,int second)
{
int auxiliary=arr[first];
arr[first]=arr[second];
arr[second]=auxiliary;
}
public int compare(int []arr,int left,int right,int root,int size)
{
int location = -1;
if(left < size && arr[left] > arr[root] )
{
if(right < size && arr[right] > arr[left])
{
swap(arr,right,root);
location = right;
}
else
{
swap(arr,left,root);
location = left;
}
}
else if(right < size && arr[right] > arr[root])
{
swap(arr,right,root);
location = right;
}
return location;
}
//Perform the operation of heap sort
public void heap(int []arr,int size,int root)
{
int left,right;
while(root!=-1)
{
left = 2*root+1;
right = 2*root+2;
root = compare(arr, left, right, root, size);
}
}
//Sort array element using heap sort
public void heap_sort(int []arr,int size)
{
for (int i = (size/2)-1; i >= 0; i--)
{
heap(arr, size, i);
}
for (int i = size-1; i >= 0; i--)
{
swap(arr, 0, i);
heap(arr, i, 0);
}
}
public void print_data(int []arr,int size)
{
for(int i = 0; i < size; i++)
{
System.out.print(" "+arr[i] );
}
System.out.print("\n");
}
public static void main(String[] args) {
MyHeap obj = new MyHeap();
//Collection of unordered sorted array
int []arr = {6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12 ,5};
//Get the size of array
int size = arr.length;
System.out.print(" Before Sort\n");
obj.print_data(arr,size);
obj.heap_sort(arr,size);
System.out.print("\n After Sort\n");
obj.print_data(arr,size);
}
}
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21
/*
C# Program
Iterative Heap Sort
*/
using System;
public class MyHeap {
//Swap two element in array
public void swap(int[] arr, int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
public int compare(int[] arr, int left, int right, int root, int size) {
int location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
swap(arr, right, root);
location = right;
} else {
swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
swap(arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
public void heap(int[] arr, int size, int root) {
int left, right;
while (root != -1) {
left = 2 * root + 1;
right = 2 * root + 2;
root = compare(arr, left, right, root, size);
}
}
//Sort array element using heap sort
public void heap_sort(int[] arr, int size) {
for (int i = (size / 2) - 1; i >= 0; i--) {
heap(arr, size, i);
}
for (int i = size - 1; i >= 0; i--) {
swap(arr, 0, i);
heap(arr, i, 0);
}
}
public void print_data(int[] arr, int size) {
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public static void Main(String[] args) {
MyHeap obj = new MyHeap();
int[]
//Collection of unordered sorted array
arr = {
6,
8,
2,
2,
7,
1,
3,
8,
21,
11,
12,
5
};
//Get the size of array
int size = arr.Length;
Console.Write(" Before Sort\n");
obj.print_data(arr, size);
obj.heap_sort(arr, size);
Console.Write("\n After Sort\n");
obj.print_data(arr, size);
}
}
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21
<?php
/*
Php Program
Iterative Heap Sort
*/
class MyHeap {
//Swap two element in array
public function swap(&$arr, $first, $second) {
$auxiliary = $arr[$first];
$arr[$first] = $arr[$second];
$arr[$second] = $auxiliary;
}
public function compare(&$arr, $left, $right, $root, $size) {
$location = -1;
if ($left < $size && $arr[$left] > $arr[$root]) {
if ($right < $size && $arr[$right] > $arr[$left]) {
$this->swap($arr, $right, $root);
$location = $right;
} else {
$this->swap($arr, $left, $root);
$location = $left;
}
} else
if ($right < $size && $arr[$right] > $arr[$root]) {
$this->swap($arr, $right, $root);
$location = $right;
}
return $location;
}
//Perform the operation of heap sort
public function heap(&$arr, $size, $root) {
$left = 0;
$right = 0;
while ($root != -1) {
$left = 2 *$root + 1;
$right = 2 *$root + 2;
$root = $this->compare($arr, $left, $right, $root, $size);
}
}
//Sort array element using heap sort
public function heap_sort(&$arr, $size) {
for ($i = (intval($size / 2)) - 1; $i >= 0; $i--) {
$this->heap($arr, $size, $i);
}
for ($i = $size - 1; $i >= 0; $i--) {
$this->swap($arr, 0, $i);
$this->heap($arr, $i, 0);
}
}
public function print_data($arr, $size) {
for ($i = 0; $i < $size; $i++) {
echo(" ". $arr[$i]);
}
echo("\n");
}
}
function main() {
$obj = new MyHeap();
//Collection of unordered sorted array
$arr = array(6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12, 5);
//Get the size of array
$size = count($arr);
echo(" Before Sort\n");
$obj->print_data($arr, $size);
$obj->heap_sort($arr, $size);
echo("\n After Sort\n");
$obj->print_data($arr, $size);
}
main();
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21
/*
Node Js Program
Iterative Heap Sort
*/
class MyHeap {
//Swap two element in array
swap(arr, first, second) {
var auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
compare(arr, left, right, root, size) {
var location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
this.swap(arr, right, root);
location = right;
} else {
this.swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
this.swap(arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
heap(arr, size, root) {
var left = 0;
var right = 0;
while (root != -1) {
left = 2 *root + 1;
right = 2 *root + 2;
root = this.compare(arr, left, right, root, size);
}
}
//Sort array element using heap sort
heap_sort(arr, size) {
for (var i = (parseInt(size / 2)) - 1; i >= 0; i--) {
this.heap(arr, size, i);
}
for (var i = size - 1; i >= 0; i--) {
this.swap(arr, 0, i);
this.heap(arr, i, 0);
}
}
print_data(arr, size) {
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
}
function main(args) {
var obj = new MyHeap();
//Collection of unordered sorted array
var arr = [6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12, 5];
//Get the size of array
var size = arr.length;
process.stdout.write(" Before Sort\n");
obj.print_data(arr, size);
obj.heap_sort(arr, size);
process.stdout.write("\n After Sort\n");
obj.print_data(arr, size);
}
main();
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21
# Python 3 Program
# Iterative Heap Sort
class MyHeap :
# Swap two element in array
def swap(self, arr, first, second) :
auxiliary = arr[first]
arr[first] = arr[second]
arr[second] = auxiliary
def compare(self, arr, left, right, root, size) :
location = -1
if (left < size and arr[left] > arr[root]) :
if (right < size and arr[right] > arr[left]) :
self.swap(arr, right, root)
location = right
else :
self.swap(arr, left, root)
location = left
elif (right < size and arr[right] > arr[root]) :
self.swap(arr, right, root)
location = right
return location
# Perform the operation of heap sort
def heap(self, arr, size, root) :
left = 0
right = 0
while (root != -1) :
left = 2 * root + 1
right = 2 * root + 2
root = self.compare(arr, left, right, root, size)
# Sort array element using heap sort
def heap_sort(self, arr, size) :
i = (int(size / 2)) - 1
while (i >= 0) :
self.heap(arr, size, i)
i -= 1
i = size - 1
while (i >= 0) :
self.swap(arr, 0, i)
self.heap(arr, i, 0)
i -= 1
def print_data(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print("\n", end = "")
def main() :
obj = MyHeap()
arr = [6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12, 5]
size = len(arr)
print(" Before Sort\n", end = "")
obj.print_data(arr, size)
obj.heap_sort(arr, size)
print("\n After Sort\n", end = "")
obj.print_data(arr, size)
if __name__ == "__main__":
main()
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21
# Ruby Program
# Iterative Heap Sort
class MyHeap
# Swap two element in array
def swap(arr, first, second)
auxiliary = arr[first]
arr[first] = arr[second]
arr[second] = auxiliary
end
def compare(arr, left, right, root, size)
location = -1
if (left < size && arr[left] > arr[root])
if (right < size && arr[right] > arr[left])
self.swap(arr, right, root)
location = right
else
self.swap(arr, left, root)
location = left
end
elsif (right < size && arr[right] > arr[root])
self.swap(arr, right, root)
location = right
end
return location
end
# Perform the operation of heap sort
def heap(arr, size, root)
left = 0
right = 0
while (root != -1)
left = 2 * root + 1
right = 2 * root + 2
root = self.compare(arr, left, right, root, size)
end
end
# Sort array element using heap sort
def heap_sort(arr, size)
i = (size / 2) - 1
while (i >= 0)
self.heap(arr, size, i)
i -= 1
end
i = size - 1
while (i >= 0)
self.swap(arr, 0, i)
self.heap(arr, i, 0)
i -= 1
end
end
def print_data(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
end
def main()
obj = MyHeap.new()
arr = [6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12, 5]
size = arr.length
print(" Before Sort\n")
obj.print_data(arr, size)
obj.heap_sort(arr, size)
print("\n After Sort\n")
obj.print_data(arr, size)
end
main()
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21
/*
Scala Program
Iterative Heap Sort
*/
class MyHeap {
//Swap two element in array
def swap(arr: Array[Int], first: Int, second: Int): Unit = {
val auxiliary: Int = arr(first);
arr(first) = arr(second);
arr(second) = auxiliary;
}
def compare(arr: Array[Int], left: Int, right: Int, root: Int, size: Int): Int = {
var location: Int = -1;
if (left < size && arr(left) > arr(root)) {
if (right < size && arr(right) > arr(left)) {
this.swap(arr, right, root);
location = right;
} else {
this.swap(arr, left, root);
location = left;
}
} else
if (right < size && arr(right) > arr(root)) {
this.swap(arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
def heap(arr: Array[Int], size: Int, location : Int): Unit = {
var left: Int = 0;
var right: Int = 0;
var root : Int = location;
while (root != -1) {
left = 2 * root + 1;
right = 2 * root + 2;
root = this.compare(arr, left, right, root, size);
}
}
//Sort array element using heap sort
def heap_sort(arr: Array[Int], size: Int): Unit = {
var i: Int = ((size / 2).toInt) - 1;
while (i >= 0) {
this.heap(arr, size, i);
i -= 1;
}
i = size - 1;
while (i >= 0) {
this.swap(arr, 0, i);
this.heap(arr, i, 0);
i -= 1;
}
}
def print_data(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
print("\n");
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyHeap = new MyHeap();
var arr: Array[Int] = Array(6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12, 5);
val size: Int = arr.length;
print(" Before Sort\n");
obj.print_data(arr, size);
obj.heap_sort(arr, size);
print("\n After Sort\n");
obj.print_data(arr, size);
}
}
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21
/*
Swift Program
Iterative Heap Sort
*/
class MyHeap {
//Swap two element in array
func swap(_ arr: inout[Int], _ first: Int, _ second: Int) {
let auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
func compare(_ arr: inout [Int], _ left: Int, _ right: Int, _ root: Int, _ size: Int) -> Int {
var location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
self.swap(&arr, right, root);
location = right;
} else {
self.swap(&arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
self.swap(&arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
func heap(_ arr: inout [Int], _ size: Int, _ location: Int) {
var left = 0;
var right = 0;
var root = location;
while (root != -1) {
left = 2 * root + 1;
right = 2 * root + 2;
root = self.compare(&arr, left, right, root, size);
}
}
//Sort array element using heap sort
func heap_sort(_ arr: inout [Int], _ size: Int) {
var i = (size / 2) - 1;
while (i >= 0) {
self.heap(&arr, size, i);
i -= 1;
}
i = size - 1;
while (i >= 0) {
self.swap(&arr, 0, i);
self.heap(&arr, i, 0);
i -= 1;
}
}
func print_data(_ arr: [Int], _ size: Int) {
var i = 0;
while (i < size) {
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
func main() {
let obj = MyHeap();
var arr = [6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12, 5];
let size = arr.count;
print(" Before Sort\n", terminator: "");
obj.print_data(arr, size);
obj.heap_sort(&arr, size);
print("\n After Sort\n", terminator: "");
obj.print_data(arr, size);
}
main();
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment