2023-11-15
Introduction
Summary
keywords
TODO
HW
Exercise*
Next time
Heap
Binary tree
Array representation of binary tree
Complete binary tree
Binary tree
height, depth 0 is root, depth 1 is the next level, ..
Array representation
store higher leaves first, left to right.
Wee need to preserve..
Element value itself
parent-child relationship.
If a node is at node i
the left child is at 2*i, right child is at 2*i+1, its parent is at [i/2]
Full binary tree
every leaves of height is filled.
2^h-1Nodes height is log n ?
Complete binary tree
there should be no empty parts in array representation
![[Pasted image 20231115145210.png]] up is a complete binary tree. down is not a complete binary tree.
Max heap & Min heap
Max heap is
a complete binary tree
parent element are always bigger than child
Min heap is
a complete binary tree
parent element are always smaller than child.
This doen't mean that heap is a sorted array. **They only guarantee the min, or max value.
Insertion operation in MaxHeap
You first insert the new element at the bottom, and move to the top
compare with parent, and if parent is smaller, swap. This way, the property of complete binary tree is preserved.
Time complexity of insertion
The time complexity of insertion is $O(\log{n})$ at maximum, which is the height of the tree. minimum O(1), maximum $O(\log{n})$
Removal operation in Max Heap.
you only pop the top of the heap.
popping is easy, but you need to readjust the remaining elements.
How to readjust?
end element move to the front, and compare with the children.
Time complexity of removal&readjust.
The time complexity of readjustment is minimum O(1), maximum $O(\log{n})$
HeapSort
if you pop element one by one from a heap and combine it, it results a sorted array.
![[Pasted image 20231115152534.png]] we do n removal&readjust. so time complexity is $O(n\log n)$.
#todo :write about time complexity, and comparison
Heapify
Adjusting downwards
heap creating time complexity to $O(n)$
From the back element, check if the downards tree is a heap. Else, make it a heap. number of swaps for each height is $log n$...?
Last updated