dg-publish: true

study/datastructure

A Heap is a complete binary tree, where all levels of tree, except
Possibly the last level, are fully filled

![[Pasted image 20231023104516.png|300]]

Min Heap

• A parent node has a key that is smaller than its child nodes
• The root node has the smallest key

![[Pasted image 20231023104907.png|300]]

Common Operations

• Get the element with the minimum or maximum key
• Remove the element with the minimum or maximum key
• Insert a new element

Applications

• Priority Queues (e.g. CPU job-scheduling)
• Sorting (via HeapSort)

Implementation

Use an array to represent a Min Heap
![[Pasted image 20231023110447.png|300]]

![[Pasted image 20231023110228.png|300]]

i=index of array
Parent node : i
	Left node: 2*i+1
	Right node: 2*i+2
Find a node's parents; (i-1)/2

Insert

Place new element 0 at the end of Heap
![[Pasted image 20231023132640.png]]

Compare new element 0 with parent element 4;swap as new element 0 is smaller
![[Pasted image 20231023132758.png]]

Swap new element 0 with parent element 1 as new element is smaller;stop as heap property is restored
![[Pasted image 20231023132941.png]]

Remove

Replace root element 1 with last element 5
![[Pasted image 20231023133035.png]]

Child element 2 is the smallest,sqap with target element 5
![[Pasted image 20231023133128.png]]

Child element 3 is the smallest,swap with target element 5; stop as heap property is restored
![[Pasted image 20231023133142.png]]

Heap Sort

• Given a list of inputs, how to sort its key in ascending order?
  • Construct a Min Heap using the inputs
  • While Min Heap not empty
    • Extract the minimum key