Logo

Navigation
  • Home
  • Services
    • ERP Solutions
    • Implementation Solutions
    • Support and Maintenance Solutions
    • Custom Solutions
    • Upgrade Solutions
    • Training and Mentoring
    • Web Solutions
    • Production Support
    • Architecture Designing
    • Independent Validation and Testing Services
    • Infrastructure Management
  • Expertise
    • Microsoft Development Expertise
    • Mobile Development
    • SQL Server Database and BI
    • SAP BI, SAP Hana, SAP BO
    • Oracle and BI
    • Oracle RAC
  • Technical Training
    • Learn Data Management
      • Business Intelligence
      • Data Mining
      • Data Modeling
      • Data Warehousing
      • Disaster Recovery
    • Learn Concepts
      • Application Development
      • Client Server
      • Cloud Computing Tutorials
      • Cluster Computing
      • CRM Tutorial
      • EDI Tutorials
      • ERP Tutorials
      • NLP
      • OOPS
      • Concepts
      • SOA Tutorial
      • Supply Chain
      • Technology Trends
      • UML
      • Virtualization
      • Web 2.0
    • Learn Java
      • JavaScript Tutorial
      • JSP Tutorials
      • J2EE
    • Learn Microsoft
      • MSAS
      • ASP.NET
      • ASP.NET 2.0
      • C Sharp
      • MS Project Training
      • Silverlight
      • SQL Server 2005
      • VB.NET 2005
    • Learn Networking
      • Networking
      • Wireless
    • Learn Oracle
      • Oracle 10g
      • PL/SQL
      • Oracle 11g Tutorials
      • Oracle 9i
      • Oracle Apps
    • Learn Programming
      • Ajax Tutorial
      • C Language
      • C++ Tutorials
      • CSS Tutorial
      • CSS3 Tutorial
      • JavaScript Tutorial
      • jQuery Tutorial
      • MainFrame
      • PHP Tutorial
      • VBScript Tutorial
      • XML Tutorial
    • Learn Software Testing
      • Software Testing Types
      • SQA
      • Testing
  • Career Training
    • Career Improvement
      • Career Articles
      • Certification Articles
      • Conflict Management
      • Core Skills
      • Decision Making
      • Entrepreneurship
      • Goal Setting
      • Life Skills
      • Performance Development
      • Personal Excellence
      • Personality Development
      • Problem Solving
      • Relationship Management
      • Self Confidence
      • Self Supervision
      • Social Networking
      • Strategic Planning
      • Time Management
    • Education Help
      • Career Tracks
      • Essay Writing
      • Internship Tips
      • Online Education
      • Scholarships
      • Student Loans
    • Managerial Skills
      • Business Communication
      • Business Networking
      • Facilitator Skills
      • Managing Change
      • Marketing Management
      • Meeting Management
      • Process Management
      • Project Management
      • Project Management Life Cycle
      • Project Management Process
      • Project Risk Management
      • Relationship Management
      • Task Management
      • Team Building
      • Virtual Team Management
    • Essential Life Skills
      • Anger Management
      • Anxiety Management
      • Attitude Development
      • Coaching and Mentoring
      • Emotional Intelligence
      • Stress Management
      • Positive Thinking
    • Communication Skills
      • Conversation Skills
      • Cross Culture Competence
      • English Vocabulary
      • Listening Skills
      • Public Speaking Skills
      • Questioning Skills
    • Soft Skills
      • Assertive Skills
      • Influence Skills
      • Leadership Skills
      • Memory Skills
      • People Skills
      • Presentation Skills
    • Finding a Job
      • Etiquette Tips
      • Group Discussions
      • HR Interviews
      • Interview Notes
      • Job Search Tips
      • Resume Tips
      • Sample Resumes
 

C Algorithms – Heap Sort

By Exforsys | on September 11, 2011 |
C Algorithms

Heapsort is a comparison based algorithm. It bases on building a heap tree from the data set, and then it removes the greatest element from the tree and adds it to the end of the sorted list. There are two ways to do this, either to add the highest value to the root of the tree, or as one of the left/right child with the greatest depth.

How it works:

The heap tree is built according to the data set. Then the greatest value is move to the root of the tree, and then it is removed. This represents the highest value from the data set, so it is added to the end of the sorted list. Next, the heap is reconstructed, and the second highest value is added to the top and then it is removed. This continues until the tree is empty and the list is full.

Step by step example :

Having the following list, let’s try to use heapsort to arrange the numbers from lowest to greatest:

Unsorted list: 15, 19, 10, 7, 17, 6.

Building the heap tree:

Start with the rightmost node at height 1 – the node at position 3 = Size/2. It has one greater child and has to be percolated down:

And it will look like this:

Then, we check the children of 19, but both are smaller so no swap is needed:

The children of 15 are 19 and 16, and is smaller, so a swap is required:

Also, 15 is smaller than 17 one of the children, so it is again time to swap :

Now the heap was built.

Next, it is time to sort the heap:

19, being the highest value, was removed from the top:

Swap 19 with the last element of the heap (As 10 will be adjusted in the heap, its cell will no longer be a part of the heap. Instead it becomes a cell from the sorted array ):

The element 10 will have to go down in the tree:

And again down one more level, 10 is less that 15, so it cannot be inserted in the previous hole :

 

Now 10 has found the right spot:

The next greatest element is 17, which has to be removed :

Also, swap 17 with the last element of the heap. As 10 will be adjusted in the heap, its cell will no longer be a part of the heap, instead it becomes a cell from the sorted array:

The element 10 is less than the children of the hole, and we percolate the hole down:

Insert 10 in the hole

Delete the next biggest element which is 16:

Swap 16 with the last element of the heap. As 7 will be adjusted in the heap, its cell will no longer be a part of the heap, instead it becomes a cell from the sorted array:

Go down one level to find the right position for 7:

Remove 15:

Swap 15 with the last element of the heap. As 10 will be adjusted in the heap, its cell will no longer be a part of the heap, instead it becomes a position from the sorted array:

Store 10 in the hole (10 is greater than the children of the hole)

Remove 10:

Swap 10 with the last element of the heap. As 7 will be adjusted in the heap, its cell will no longer be a part of the heap, instead it becomes a cell from the sorted array:

Store 7 in the hole (as the only remaining element in the heap):

7 is the last element from the heap, so now the array is sorted :

Sample code:

  1.  #include< iostream >
  2. using namespace std;
  3.  
  4. void insert (int v[],int &N, int a)
  5. {
  6. 	v[N]=a;
  7. 	N++;
  8. 	int child=N-1;
  9. 	int parent=abs((child-1)/2);
  10. 	while(parent >=0 )
  11. 	{
  12. 		if(v[child]>v[parent])
  13. 		{
  14. 			v[child]=v[parent]+v[child];
  15. 			v[parent]=v[child]-v[parent];
  16. 			v[child]=v[child]-v[parent];
  17. 			child=parent;
  18. 			parent=abs((child-1)/2);
  19. 		}
  20. 		else
  21. 			parent=-1;
  22. 	}
  23. }int remove(int v[],int N)
  24. {
  25. 	int	a=v[0];
  26. 	v[0]=v[N-1];
  27. 	N--;
  28. 	int parent=0;
  29. 	int child=1;
  30. 	while(child<=N-1)
  31. 	{
  32. 		if(child+1< =N-1 && (v[child+1]>v[child]))
  33. 			child++;
  34. 		if (v[parent]< v[child])
  35. 		{
  36. 			int	aux=v[parent];
  37. 			v[parent]=v[child];
  38. 			v[child]=aux;
  39. 			parent=child;
  40. 			child=2*parent+1;}
  41. 		else
  42. 			break;
  43. 	}
  44. 	return a;
  45. }
  46. void heap_sort(int a[],int N,int v[])
  47. {
  48. 	for(int i=N-1;i>=0;i--)
  49. 	{
  50. 		N=i+1;
  51. 		a[i]=remove(v,N);
  52. 	}
  53. }
  54. void  heap_gen1(int a[],int v[],int n)
  55. {
  56. 	int N=1;
  57. 	v[0]=a[0];
  58. 	for(int i=1;i< n;i++)
  59. 	{
  60. 		insert(v,N,a[i]);
  61. 	}
  62. }
  63. void display(int a[],int n)
  64. {
  65. 	for(int i=0;i < n;i++)
  66. 	{
  67. 		cout << a[i] << " ";
  68. 	}
  69. }
  70. int main()
  71. {
  72. 	int *a=new int[100];
  73. 	int *v=new int[100];
  74. 	int n;
  75. 	cout << "Please insert the number of elements to be sorted: ";
  76. 	cin >> n;	// The total number of elements
  77. 	for(int i=0;i < n;i++)
  78. 	{
  79. 		cout << "Input " << i << " element: ";
  80. 		cin >> a[i]; // Adding the elements to the array
  81. 	}
  82. 	cout << "Unsorted list:" << endl;	// Displaying the unsorted array
  83. 	for(int i=0;i < n;i++)
  84. 	{
  85. 		cout << a[i] << " ";
  86. 	}
  87. 	heap_gen1(a,v,n);
  88. 	cout << "nGenerated Heap:n";
  89. 	display(v,n);
  90. 	cout << "nAfter sorting";
  91. 	heap_sort(a,n,v);
  92. 	cout << "n";
  93. 	display(a,n);
  94. 	return 0;
  95. }

Output:

Code explanation:

The function heap_sort is the one that is removing the top of the heap tree and making the sorting list. The implementation of the algorithm simply follows the same steps as those from the above example.

Complexity:

HeapSort’s space-complexity is O(1), just a few scalar variables. It uses a data structure known as a max-heap which is a complete binary tree where the element at any node is the maximum of itself and all its children. A tree can be stored either with pointers as per the pictorial representation we are normally used to visualize, or by mapping it to a vector. Here if a node in the tree is mapped to the ith element of an array, then its left child is at 2i, its right child is at (2i+1) and its parent is at floor(i/2). We can construct a heap by starting with a an existing heap, adding an element at the bottom of the heap, and allow it to migrate up the father chain till it finds its proper position. Complexity T(n) = O(n*log (n)).

Advantages:

  • it does not use recursion;
  • works just as fast or any data order.
  • there is no worst case scenario.

Disadvantages:

  • slower that quick and merge sort;
  • memory requirement, it requires both an array and a heap of size n;
  • not stable.

Conclusion:

HeapSort is a good sorting algorithm, with a good complexity O(n*log(n)) for worst/base/average scenario. Heapsort is an in-place algorithm, but is not a stable sort.

« « C Algorithms – Selection Sort
C Algorithms – Counting Sort » »

Author Description

Avatar

Editorial Team at Exforsys is a team of IT Consulting and Training team led by Chandra Vennapoosa.

Free Training

RSSSubscribe 392 Followers
  • Popular
  • Recent
  • C Algorithms – Insertion Sort

    September 9, 2011 - 0 Comment
  • C Algorithms – Dijkstra’s Algorithm

    September 17, 2011 - 0 Comment
  • C Algorithms – Selection Sort

    September 11, 2011 - 0 Comment
  • C Algorithms – Breadth-First Search (BFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Bubble Sort

    September 9, 2011 - 0 Comment
  • C Algorithms – Quick Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Comb Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Shell Sort

    September 10, 2011 - 0 Comment
  • C Algorithms – Counting Sort

    September 12, 2011 - 0 Comment
  • C Algorithms – Dijkstra’s Algorithm

    September 17, 2011 - 0 Comment
  • C Algorithms – Breadth-First Search (BFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Topological Sort

    September 15, 2011 - 0 Comment
  • C Algorithms – Graph Theory

    September 15, 2011 - 0 Comment
  • C Algorithms – Gnome Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Comb Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Bucket Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Quick Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Counting Sort

    September 12, 2011 - 0 Comment

Exforsys e-Newsletter

ebook
 

Related Articles

  • C Algorithms – Dijkstra’s Algorithm
  • C Algorithms – Breadth-First Search (BFS)
  • C Algorithms – Depth-First Search (DFS)
  • C Algorithms – Topological Sort
  • C Algorithms – Graph Theory

Latest Articles

  • Project Management Techniques
  • Product Development Best Practices
  • Importance of Quality Data Management
  • How to Maximize Quality Assurance
  • Utilizing Effective Quality Assurance Strategies
  • Sitemap
  • Privacy Policy
  • DMCA
  • Trademark Information
  • Contact Us
© 2023. All Rights Reserved.IT Training and Consulting
This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish.AcceptReject Read More
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT