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..

1. Element value itself

2. 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-1 Nodes 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$...?