Heap Sort Algorithm in Python

def buildHeap(lista, n): for i in range(n//2 - 1, -1, -1): heapify(lista, n, i) def heapify(lista, n, i): largest = i left = (2 * i) + 1 right = (2 * i) + 2 if left < n and lista[largest] < lista[left]: largest = left if right < n and lista[largest] < lista[right]: largest = right if largest != i: lista[i], lista[largest] = lista[largest], lista[i] heapify(lista, n, largest) def heapSort(lista): n = len(lista) buildHeap(lista, n) for i in range(n-1, 0, -1): lista[i], lista[0] = lista[0], lista[i] heapify(lista, i, 0)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 10 18:18:25 2019

@source: https://www.geeksforgeeks.org/heap-sort/

"""
# Python program for implementation of heap Sort 

# To heapify subtree rooted at index i. 
# n is size of heap 
def heapify(arr, n, i): 
	largest = i # Initialize largest as root 
	l = 2 * i + 1	 # left = 2*i + 1 
	r = 2 * i + 2	 # right = 2*i + 2 

	# See if left child of root exists and is 
	# greater than root 
	if l < n and arr[i] < arr[l]: 
		largest = l 

	# See if right child of root exists and is 
	# greater than root 
	if r < n and arr[largest] < arr[r]: 
		largest = r 

	# Change root, if needed 
	if largest != i: 
		arr[i],arr[largest] = arr[largest],arr[i] # swap 

		# Heapify the root. 
		heapify(arr, n, largest) 

# The main function to sort an array of given size 
def heapSort(arr): 
	n = len(arr) 

	# Build a maxheap. 
	for i in range(n, -1, -1): 
		heapify(arr, n, i) 

	# One by one extract elements 
	for i in range(n-1, 0, -1): 
		arr[i], arr[0] = arr[0], arr[i] # swap 
		heapify(arr, i, 0) 

heapSort(arr)

Posted by: Guest on August-22-2021

Source

Code answers related to "Heap Sort Algorithm in Python"

Code answers related to "Python"

Browse Popular Code Answers by Language

Answers for "Heap Sort Algorithm in Python"

Code answers related to "Heap Sort Algorithm in Python"

Code answers related to "Python"

Python Answers by Framework

Browse Popular Code Answers by Language

Popular Programming Languages

Advertisements

Company

Compilers

Help

Connect with us