Sunday, April 18, 2021

heap

 A MinHeap is a binary tree where the node's value is smaller than its children. (vs MaxHeap)

https://realpython.com/python-heapq-module/

https://en.wikipedia.org/wiki/Heap_(data_structure)

https://stackoverflow.com/questions/2501457/what-do-i-use-for-a-max-heap-implementation-in-python

https://www.quora.com/What-are-the-time-complexities-of-heap

insertion O(logn)

deletion O(logn) to remove the first node and reorder to maintain the heap


def heapsort(nums):
    h = []
    for i in range(len(nums)):
        heapq.heappush(h, nums[i])
        print('h',h)
    for i in range(len(nums)):
        print('pop',heapq.heappop(h))
heapsort([29,38,2,10,1])

No comments: