CODEWITHSUNDEEP
data-structuresamortized-analysis
mammy wood
mammy wood

Reputation: 143

amortized analysis on a binary heap

So a regular binary heap has an operation extract_min which is O(log(n)) worst time. Suppose the amortized cost of extract_min is O(1). Let n be the size of the heap

So a sequence where we have n extract_min operations performed and it initially contained n elements. Does this mean that the entire sequence would be processed in O(n) time since each operation is O(1)?

Upvotes: 1

Views: 1312

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59253

Lets get this out of the way first: Removing ALL the elements in a heap via extract_min operations takes O(N log N) time.

This is a fact, so when you ask "Does constant amortized time extract_min imply linear time for removing all the elements?", what you are really asking is "Can extract_min take constant amortized time even though it takes O(N log N) time to extract all the elements?"

The answer to this actually depends on what operations the heap supports.

If the heap supports only the add and extract_min operations, then every extract_min that doesn't fail (in constant time) must correspond to a previous add. We can then say that add takes amortized O(log N) time, and extract_min take amortized O(1) time, because we can assign all of its non-constant costs to a previous add.

If the heap supports an O(N) time make_heap operation (amortized or not), however, then its possible to perform N extract_min operations without doing anything else that adds up to O(N log N) time. The whole O(N log N) cost would then have to be assigned to the N extract_min operations, and we could not claim that extract_min takes amortized constant time.

Upvotes: 1

Related Questions