Content deleted Content added
style - get the italics right |
Correct heap find-maximum and find-minimum, with citation |
||
Line 63:
| Unsorted [[linked list]]
| ''O''(1)
| ''O''(1)<ref name="listdelete">{{cite book |title=[[Introduction to Algorithms]] |publisher=The College of Information Sciences and Technology at Penn State|isbn=9780262530910|authors=Cormen, Leiserson, Rivest|quote=LIST-DELETE runs in ''O''(1) time, but if we wish to delete an element with a given key, Θ(n) time is required in the worst case because we must first call LIST-SEARCH.}}</ref>
| N/A
| ''O''(''n'')
Line 97:
| N/A
| ''O''(''n'')
| ''O''(1) for a ''min-heap''<br>''O''(''n'') for a ''max-heap''<ref name="heap">{{cite book |title=Introduction to Algorithms|publisher=The College of Information Sciences and Technology at Penn State|isbn=9780262530910|authors=Cormen, Leiserson, Rivest|quote=There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satisfy a '''heap property'''... the largest element in a max-heap is stored at the root... The smallest element in a min-heap is at the root... The operation HEAP-MAXIMUM returns the maximum heap element in Θ(1) time by simply returning the value ''A''[1] in the heap.}}</ref>
| ''O''(1) for a ''max-heap''<br>''O''(''n'') for a ''min-heap''<ref name="heap" />
| ''O''(''n'')
|-
| |||