Implementation of Heap
The table below indicates where methods are implemented and the time
complexity of these methods. Some methods are
implemented in more than one place. When this
happens, each entry overrides the entries to its left. When an entry says "based on
iterator" or "traverse iterator" or "uses size," then the time
complexity depends on the iterator or size method.
|
|
Heap Implementation
|
Abstract
Container
|
Abstract
Heap
|
Array
Heap
|
|
|
constructor ()
|
O(1)
|
O(1)
|
O(1)
|
|
|
constructor (Collection
col)
|
|
|
O(n log n)
|
|
|
constructor (Iterator
iter)
|
|
|
O(n log n)
|
|
|
constructor (Iterator
iter, int initialCapacity)
|
|
|
O(n log n)
|
|
|
constructor (int
initialCapacity)
|
|
|
O(1)
|
|
|
|
|
|
|
| boolean
|
add (Object item)
|
|
|
O(log n)
|
| void
|
clear ()
|
O(1)
|
|
O(1)
|
| Object
|
clone ()
|
|
|
O(n)
|
| Collection
|
collectionView ()
|
based on iterator
|
|
|
| boolean
|
equals (Object other)
|
|
traverse iterator
|
|
| int
|
hashCode ()
|
traverse iterator
|
|
|
| boolean
|
isEmpty
|
uses size method
|
|
|
| Iterator
|
iterator ()
|
abstract
|
|
O(n log n)
|
| Object
|
peek ()
|
|
|
O(1)
|
| Object
|
pop ()
|
|
|
O(log n)
|
| int
|
size ()
|
O(1)
|
|
|
| static Object []
|
sort (Object a[])
|
|
O(n log n)
|
|
| static Object []
|
sort (Collection col)
|
|
O(n log n)
|
|
| Object []
|
toArray ()
|
traverse iterator
|
|
|
| String
|
toString ()
|
traverse iterator
|
|
|