CODEWITHSUNDEEP
algorithmdata-structuresheap
cryptomanic
cryptomanic

Reputation: 6316

How to insert elements to a sorted heap such that it remains sorted?

Inserting an element in sorted heap at the end takes O(1). But I want to insert in such a way such that it remain sorted. Achieving this in O(n) is not a big deal.

How can I take advantage of that it is sorted? Finding Appropriate position via binary search will take O(logn). But insertion via swapping will again be of Order n. How I can reduce the time complexity? Please help.

Upvotes: 4

Views: 2858

Answers (1)

Zotta
Zotta

Reputation: 2603

This is how you normally insert into a heap, that is just a heap and not a sorted list:

A heap is a hirachical structure. Every element has up to 2 children. To insert, you just append at the end and then compare it to its parent, wich can be determined by the position of the element. If the parent is bigger, then you swap the parent with the new element. Repeat until either the new element is bigger than its parent, or the new element has become the first/top element. That way, the smallest element is always the first element.

This operation will take O(log n) operations at most.

After reading the comments, what you actually want is not a classical heap, but a sorted tree implemented using pointers or array indices. Search for red black tree.

Upvotes: 1

Related Questions