Difference between revisions of "TADM2E 4.13"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Removed extra "of")
 
Line 1: Line 1:
 
1) Finding the maximum element is O(1) in both a max-heap (the root of the heap) and a sorted array (the last element in the array), so for this operation, both data structures are equally optimal.
 
1) Finding the maximum element is O(1) in both a max-heap (the root of the heap) and a sorted array (the last element in the array), so for this operation, both data structures are equally optimal.
  
2) Assuming the index of of the element is known, a deletion on a heap costs O(log n) time to bubble down.  A sorted array requires all elements to be updated leading to a O(n) operation.
+
2) Assuming the index of the element is known, a deletion on a heap costs O(log n) time to bubble down.  A sorted array requires all elements to be updated leading to a O(n) operation.
  
 
3) A heap can be formed in O(n) time.  The sorted array will require a sort costing O(n log n).
 
3) A heap can be formed in O(n) time.  The sorted array will require a sort costing O(n log n).
  
 
4) Finding the minimum element in a max-heap requires visiting each of the leaf nodes in the worst case, i.e. is an O(n) operation. Finding the minimum element in a sorted array is an O(1) operation (it's the first element), so the sorted array performs (asymptotically) better.
 
4) Finding the minimum element in a max-heap requires visiting each of the leaf nodes in the worst case, i.e. is an O(n) operation. Finding the minimum element in a sorted array is an O(1) operation (it's the first element), so the sorted array performs (asymptotically) better.

Latest revision as of 03:25, 15 January 2019

1) Finding the maximum element is O(1) in both a max-heap (the root of the heap) and a sorted array (the last element in the array), so for this operation, both data structures are equally optimal.

2) Assuming the index of the element is known, a deletion on a heap costs O(log n) time to bubble down. A sorted array requires all elements to be updated leading to a O(n) operation.

3) A heap can be formed in O(n) time. The sorted array will require a sort costing O(n log n).

4) Finding the minimum element in a max-heap requires visiting each of the leaf nodes in the worst case, i.e. is an O(n) operation. Finding the minimum element in a sorted array is an O(1) operation (it's the first element), so the sorted array performs (asymptotically) better.