# 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$...?