Difference between revisions of "TADM2E 4.13"
(Recovering wiki) |
|||
| (3 intermediate revisions by 3 users not shown) | |||
| 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. (The max-heap is ''marginally'' faster, since the array length doesn't need to be accessed, but this splits hairs.) |
| − | 2) Assuming the index | + | 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 01:03, 1 August 2020
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. (The max-heap is marginally faster, since the array length doesn't need to be accessed, but this splits hairs.)
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.
