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

inserting element in sorted heap @ end takes o(1). want insert in such way such remain sorted. achieving in o(n) not big deal.

how can take advantage of sorted? finding appropriate position via binary search take o(logn). insertion via swapping again of order n. how can reduce time complexity? please help.

this how insert heap, heap , not sorted list:

a heap hirachical structure. every element has 2 children. insert, append @ end , compare parent, wich can determined position of element. if parent bigger, swap parent new element. repeat until either new element bigger parent, or new element has become first/top element. way, smallest element first element.

this operation take o(log n) operations @ most.

after reading comments, want not classical heap, sorted tree implemented using pointers or array indices. search red black tree.