What is the time per operation of merging, insertion and deletion operations in a skew heap?

Category: QuestionsWhat is the time per operation of merging, insertion and deletion operations in a skew heap?
Editor">Editor Staff asked 4 weeks ago

What is the time per operation of merging, insertion and deletion operations in a skew heap?
 
(a) O(N)
 
(b) O(log N)
 
(c) O(N log N)
 
(d) O(N^2)
 
I need to ask this question from Heap topic in division Heap of Data Structures & Algorithms I
 
This question was posed to me during an interview.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Correct answer is (b) O(log N)
 
Best explanation: Skew heaps support merging, insertion and deletion all effectively in O(log N) time per operation.