# Heap Sort Program in C

By | October 4, 2016

Learn how to implement Heap Sort Program in C using Array data structure. The heap sort algorithm in C programming can be implemented using Heapify or with Linked Lists.

## What is Heap Sort Algorithm?

A Heap is a binary tree that satisfies the two properties:

• Heap Order Property: The key value in every node must be greater than or equal to the key values in both its child nodes.
• Structure Property: All the levels have a maximum number of nodes except possibly the last level since all the last level nodes occur to the left.

The Heap Sort algorithm is performed in 2 phases:

• Building a Max Heap from the given elements stored in the array.
• Continuously deleting the root node until there is only one element/node left in the tree.

The root node of the heap always has the largest element. If we successively delete the root node, elements can be fetched in descending order by deleting them one by one. Now, these deleted elements can be stored in a separate array.

Note: This Heap Sort Program in C is compiled with GNU GCC Compiler and developed using gEdit Editor and Terminal in Linux Ubuntu Operating System.

#### Heap Sort Algorithm Analysis

Here’s the heap sort time complexity analysis. The first phase of this algorithm has a running time of O(n). However, the delete of the nodes takes O(log n) time, making the complexity of the second phase as O(n log n).

Heap Sort is a stable sort and it is an in-place sorting algorithm. The space complexity of the heap sort algorithm is O(1). This algorithm is preferable for larger lists. The average case complexity, worst-case complexity, and best case complexity of this algorithm is O(n log n).

#### Output

If you have any compilation errors or doubts about Heap Sort Program in C, let us know about it in the comment section below.

## 3 thoughts on “Heap Sort Program in C”

1. Tej Rakhasiya

I believe Heap Sort algorithm is the fastest of all the other sorting algorithms, Isn’t it?

2. Vivek Rathod

I think understanding binary trees is a prerequisite for this sorting algorithm.

3. Sanmesh Sawant