w3resource

Python: Pushing all values onto a heap and then popping off the smallest values one at a time


3. Heapsort Implementation

Write a Python program to implement heapsort by pushing all values onto a heap and then popping off the smallest values one at a time.

Sample Solution:

Python Code:

import heapq as hq
def heapsort(iterable):
    h = []
    for value in iterable:
        hq.heappush(h, value)
    return [hq.heappop(h) for i in range(len(h))]
print(heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]))

Sample Output:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Flowchart:

Python heap queue algorithm: Pushing all values onto a heap and then popping off the smallest values one at a time.

For more Practice: Solve these Related Problems:

  • Write a Python program to implement heapsort by inserting all elements into a heap using heapq.heapify, then repeatedly calling heappop to produce a sorted list.
  • Write a Python script to demonstrate heapsort on a large list of integers and compare its output with Python’s built-in sorted() function.
  • Write a Python function that sorts a list using the heap queue algorithm and prints the intermediate heap states during sorting.
  • Write a Python program to implement heapsort on a list of floating-point numbers and then validate that the final list is in ascending order.

Go to:


Previous: Write a Python program to find the three smallest integers from a given list of numbers using Heap queue algorithm.
Next: Write a Python function which accepts an arbitrary list and converts it to a heap using Heap queue algorithm.

Python Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.