Titsjgrosdnle Here

4) insert(): Inserting a new key takes O(Logn) time. We add a new key at the end of the tree. IF new key is greater than its parent, then we don’t need to do anything. Otherwise, we need to traverse up to fix the violated heap property.

4) insert(): Inserting a new key takes O(Logn) time. We add a new key at the end of the tree. IF new key is greater than its parent, then we don’t need to do anything. Otherwise, we need to traverse up to fix the violated heap property.

5) delete(): Deleting a key also takes O(Logn) time. We replace the key to be deleted with minum infinite by calling decreaseKey(). After decreaseKey(), the minus infinite value must reach root, so we call extractMin() to remove the key.

Decrease or increase key

The decrease key operation replaces the value of a node with a given value with a lower value, and the increase key operation does the same but with a higher value. This involves finding the node with the given value,

changing the value, and then down-heapifying or up-heapifying to restore the heap property.

changing the value, and then down-heapifying or up-heapifying to restore the heap property.

Decrease key can be done as follows:

• Find the index of the element we want to modify
• Decrease the value of the node
• Down-heapify (assuming a max heap) to restore the heap property

Increase key can be done as follows:

• Find the index of the element we want to modify
• Increase the value of the node
• Up-heapify (assuming a max heap) to restore the heap property

Summary of running times

Operation	find-min	delete-min	insert	decrease-key	meld
Binary[17]	Θ(1)	Θ(log n)	O(log n)	O(log n)	Θ(n)
Leftist	Θ(1)	Θ(log n)	Θ(log n)	O(log n)	Θ(log n)
Binomial[17][18]	Θ(1)	Θ(log n)	Θ(1)[c]	Θ(log n)	O(log n)[d]
Fibonacci[17][19]	Θ(1)	O(log n)[c]	Θ(1)	Θ(1)[c]	Θ(1)
Pairing[20]	Θ(1)	O(log n)[c]	Θ(1)	o(log n)[c][e]	Θ(1)
Brodal[23][f]	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Rank-pairing[25]	Θ(1)	O(log n)[c]	Θ(1)	Θ(1)[c]	Θ(1)
Strict Fibonacci[26]	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
2–3 heap[27]	O(log n)	O(log n)[c]	O(log n)[c]	Θ(1)	?