Sorting

[ahasusie]

select sort merge sort heap sort

[ahasusie]

heap a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C.

The heap is one maximally efficient implementation of an abstract data type called a priority queue, and in fact priority queues are often referred to as "heaps", regardless of how they may be implemented. A common implementation of a heap is the binary heap, in which the tree is a binary tree

a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued

python has a module: heapq

# heap usually represented as an array
arr[(i-1)/2]    # arr[i]'s parent
arr[2*i+1]     # left child
arr[2*i+2]     # right child

heapq is a binary heap, with O(log n) push and O(log n) pop https://stackoverflow.com/questions/38806202/whats-the-time-complexity-of-functions-in-heapq-library

215. Kth Largest Element in an Array

     
     import heapq
     # heapify([iterable]) eaquls to following code snippet
     # h = []
     # for val in nums:
     #     heapq.heappush(h, val)

max heap

def findKthLargest(nums, k): nums = [-num for num in nums] heapq.heapify(nums) res = float('inf') for _ in range(k): res = heapq.heappop(nums) return -res

min heap

def findKthLargest1(nums, k): minHeap = [-float('inf')] * k heapq.heapify(minHeap) for n in nums: if n > minHeap[0]: heapq.heappop(minHeap) heapq.heappush(minHeap, n) return minHeap[0]

def heapsort(nums): h = [] for val in nums: heapq.heappush(h, val) print h return [heapq.heappop(h) for i in range(len(h))]

[ahasusie]

python heapq build min heap, which means parent is less than or equal to its children.

heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]