Is it possible to insert a element to a heap or delete a element from a heap when we implement the heap with array with time complexity O(1)?

CodePudding user response：

Insertion? no. If you want it to be a heap you need to sort while inserting, so I guess you end up having log-n anyway.

Deletion? maybe. If you associate the heap with a map where the inserted value is the map key and the map value is the position of the inserted value into the heap, then you can find the position of the element in constant time, and delete it as well in constant time

CodePudding user response：

No, this isn't possible - at least, assuming that the only way to determine the relative ordering of elements is by making comparisons.

Suppose you could do this. Then we could sort a list of n items in time O(n) as follows:

• Insert all n elements into the heap in time O(n).
• Repeatedly do the following:
  • Find the smallest element in the heap in time O(1).
  • Remove that element from the heap in time O(1).

Overall, this would give an O(n)-time comparison-based sorting algorithm, which is impossible because no such algorithm exists.