Question

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.

Answer 1

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.