Skip to main content

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
Last updated on by Kalkicode




Comment

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