heap Algorithm
Heap sort algorithm is a comparison-based sorting technique that utilizes a special data structure known as a binary heap. It is an in-place sorting algorithm, meaning that it doesn't require any additional memory to be allocated for temporary storage. Heap sort works by first building a binary heap (either a max-heap or a min-heap) from the input data, and then repeatedly extracting the maximum or minimum element from the heap and inserting it into a sorted array. This process continues until the heap becomes empty and the sorted array contains all the elements from the original input data.
A binary heap is essentially a complete binary tree with the property that each parent node is either greater than or equal to (in case of a max-heap) or less than or equal to (in case of a min-heap) its child nodes. Heap sort takes advantage of this property by ensuring that the largest or smallest element is always at the root of the heap, making it easy to extract and place in the sorted array. After extracting the root element, the algorithm restores the heap property by moving elements within the heap, a process called "heapifying". This "heapify" operation is repeated until the entire input data has been sorted. The time complexity of heap sort is O(n log n) in the worst, average, and best cases, making it an efficient and reliable sorting algorithm for various applications.
#!/usr/bin/python3
class Heap(object):
"""
>>> unsorted = [103, 9, 1, 7, 11, 15, 25, 201, 209, 107, 5]
>>> h = Heap()
>>> h.build_heap(unsorted)
>>> h.display()
[209, 201, 25, 103, 107, 15, 1, 9, 7, 11, 5]
>>>
>>> h.get_max()
209
>>> h.display()
[201, 107, 25, 103, 11, 15, 1, 9, 7, 5]
>>>
>>> h.insert(100)
>>> h.display()
[201, 107, 25, 103, 100, 15, 1, 9, 7, 5, 11]
>>>
>>> h.heap_sort()
>>> h.display()
[1, 5, 7, 9, 11, 15, 25, 100, 103, 107, 201]
>>>
"""
def __init__(self):
self.h = []
self.curr_size = 0
def get_left_child_index(self, i):
left_child_index = 2 * i + 1
if left_child_index < self.curr_size:
return left_child_index
return None
def get_right_child(self, i):
right_child_index = 2 * i + 2
if right_child_index < self.curr_size:
return right_child_index
return None
def max_heapify(self, index):
if index < self.curr_size:
largest = index
lc = self.get_left_child_index(index)
rc = self.get_right_child(index)
if lc is not None and self.h[lc] > self.h[largest]:
largest = lc
if rc is not None and self.h[rc] > self.h[largest]:
largest = rc
if largest != index:
self.h[largest], self.h[index] = self.h[index], self.h[largest]
self.max_heapify(largest)
def build_heap(self, collection):
self.curr_size = len(collection)
self.h = list(collection)
if self.curr_size <= 1:
return
for i in range(self.curr_size // 2 - 1, -1, -1):
self.max_heapify(i)
def get_max(self):
if self.curr_size >= 2:
me = self.h[0]
self.h[0] = self.h.pop(-1)
self.curr_size -= 1
self.max_heapify(0)
return me
elif self.curr_size == 1:
self.curr_size -= 1
return self.h.pop(-1)
return None
def heap_sort(self):
size = self.curr_size
for j in range(size - 1, 0, -1):
self.h[0], self.h[j] = self.h[j], self.h[0]
self.curr_size -= 1
self.max_heapify(0)
self.curr_size = size
def insert(self, data):
self.h.append(data)
curr = (self.curr_size - 1) // 2
self.curr_size += 1
while curr >= 0:
self.max_heapify(curr)
curr = (curr - 1) // 2
def display(self):
print(self.h)
def main():
for unsorted in [
[],
[0],
[2],
[3, 5],
[5, 3],
[5, 5],
[0, 0, 0, 0],
[1, 1, 1, 1],
[2, 2, 3, 5],
[0, 2, 2, 3, 5],
[2, 5, 3, 0, 2, 3, 0, 3],
[6, 1, 2, 7, 9, 3, 4, 5, 10, 8],
[103, 9, 1, 7, 11, 15, 25, 201, 209, 107, 5],
[-45, -2, -5],
]:
print("source unsorted list: %s" % unsorted)
h = Heap()
h.build_heap(unsorted)
print("after build heap: ", end=" ")
h.display()
print("max value: %s" % h.get_max())
print("delete max value: ", end=" ")
h.display()
h.insert(100)
print("after insert new value 100: ", end=" ")
h.display()
h.heap_sort()
print("heap sort: ", end=" ")
h.display()
print()
if __name__ == "__main__":
main()
