Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sort, sort, bubble, selection, insertion, merge sort, divide & conquer…
Sort
binary heap
-
-
properties
parent index = floor( child index / 2 )
left child index = 2 parent (base 1 system)
right child index = 2 parent + 1 (base 1 system)
left child index = 2 parent + 1(base 0 system)
right child index = 2 parent + 2 (base 0 system)
prove above based on 2^h + i as item index
hint: first item index in level h is 2^h, last is 2^(h+1)-1
if depth is h, the elem index in level h
first elem index = 2^h
last elem index = 2^(h+1) - 1
total num in level h = 2^h
total num in level h-1 = 2^(h-1)
total num in level 1 + level 2 + ... + level h-1 = 2^h - 1
total num in level h is 2^h, which is always 1 more than total item number on all above levels
last leaf node is last elem
first leaf node is the right node of last elem's parent
if totally N elems leaf node's index is from floor(N/2)+1, floor(N/2)+2, ..., N
root of a subtree >= any items in the subtree
item value always <= item values in direct parent branch
item value may be greater than upper level item values in other branches
num of leaf = num of non leaf or
num of leaf = num of non leaf + 1
num of leaf = ceiling(N / 2)
num of non-leaf = floor(N / 2)
parent index of last item = floor(N / 2)
leaf node index starts from floor(N/2) + 1
floor(N/2) -> parent index and num of internal nodes
ceiling(N/2) -> num of leaves and index of first leaf
-
-
operations
shift up(heapify up) -> insert new node or node value increased
shift down(heapify down) -> delete a node or node value decreased
delete method 1
-> update delete item value to max + 1,
-> shift up,
-> extract max once
extract max:
- delete root
- move last elem to root
- shift down
delete method 2
-> swap delete item and last item
-> remove current last item by reduce heap length by 1
-> shift down, then shift up
-
-
-
create array - O(N)
-> create a random array
-> shift down from the last non-leaf elements to the root
-> O(n) and proof
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-