TADM2E 4.13 - Revision history

Matt: Undo revision 1058 by FuckMatt (talk)

2020-08-01T01:03:41Z

Undo revision 1058 by FuckMatt (talk)

FuckMatt: Blanked the page

2020-07-31T09:36:05Z

Blanked the page

Landisdesign: Clarified minor improvement of finding first versus nth element

2019-11-21T01:50:47Z

Clarified minor improvement of finding first versus nth element

Tcaner: Removed extra "of"

2019-01-15T03:25:23Z

Removed extra "of"

Algowikiadmin: Recovering wiki

2014-09-11T18:13:29Z

Recovering wiki

New page

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.

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.

← Older revision	Revision as of 01:03, 1 August 2020
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. (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.

← Older revision		Revision as of 09:36, 31 July 2020
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. (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.

← Older revision		Revision as of 01:50, 21 November 2019
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 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.

@@ Line 1: / Line 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.
-) 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.
+) 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.
 ) A heap can be formed in O(n) time.  The sorted array will require a sort costing O(n log n).
 ) 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.