Heap and Deap

Question 1

what is Heap?

Answer 1

a complete binary tree based data structure that satisfies heap property. lebih MUDAH pake ARRAY

Question 2

jenis heap property?

Answer 2

1. min heap, yang paling kecil diatas

2. max heap, yang paling besar diatas

Question 3

implement heap dengan?

Answer 3

dapat dengan linked-list, tapi lebih mudah pake array

Question 4

Heap Sort complexity?

Answer 4

O(n.lg(n))

Question 5

Heap applications?

Answer 5

Priority Queue

djikstra, prim

Question 6

Heap merupakan implementasi yang efisien dari?

Answer 6

Priority Queue

Question 7

Heap, root di index keberapa?

Answer 7

1

Question 8

array implementation pada Heap. parent(x), left-child(x), right-child(x) apa rumusnya?

Answer 8

parent(x) = x / 2
left-child(x) = 2 * x
right-child(x) = 2 * x + 1

Question 9

Heap Complexity?

Answer 9

find-min = O(1)
insert = O(log(n))
delete-min = O(log(n))

Question 10

Min-Max Heap?

Answer 10

Root merupakan smallest element. largest element bisa sebelah kiri atau kanan anak dari root

Question 11

Deap adalah?

Answer 11

double ended heap. mirip dengan min-max heap. algorithm lebih simple dari min-max heap

Question 12

Deap properties?

Answer 12

1. root contains no element
2. left sub-tree of root is a min heap
3. right sub-tree of root is a max heap

Question 13

Pengaplikasian Heap?

Answer 13

1. priority queue
2. selection algorithm (finding min/max element, median, k-th largest element)
3. dijkstra algorithm
4. prim algorithm
5. heap sort

Question 14

upheapmax?

Answer 14

compare current node with its grandparent value, if current node larger = swap. continue upheapmax from the granparent node

Question 15

upheapmin?

Answer 15

compare current node with its grandparent value, if current node smaller = swap. continue upheapmin from the granparent node

Question 16

new node in min-level, INSERTION MIN-MAX?

Answer 16

if new node parent smaller than swap their value and UPHEAPMAX from its parent.
else UPHEAPMIN

Question 17

new node in max-level, INSERTION MIN-MAX?

Answer 17

if new node parent larger than swap their value and UPHEAPMIN from its parent
else UPHEAPMAX