Heap Sort - Revision history

Admin: /* Fast, Bottom-Up Heap Construction */

2017-08-29T03:11:54Z

Fast, Bottom-Up Heap Construction

← Older revision		Revision as of 03:11, 29 August 2017
Line 30:		Line 30:

	It is a subtle difference, but here's why this works: '''the maximum distance an element can possibly be moved is proportional to the distance from the insertion point to the point in the heap.''' This makes the runtime for a single insert O(1), because we don't have to bubble it all the way down. If runtime is proportional to the sum of the heights, then for a heap with N nodes, this is O(N).		It is a subtle difference, but here's why this works: '''the maximum distance an element can possibly be moved is proportional to the distance from the insertion point to the point in the heap.''' This makes the runtime for a single insert O(1), because we don't have to bubble it all the way down. If runtime is proportional to the sum of the heights, then for a heap with N nodes, this is O(N).

			See the "heapify" section of the Wikipedia "Heapsort" algorithm.

	<pre>		<pre>

Admin: /* Fast, Bottom-Up Heap Construction */

2017-08-29T03:11:32Z

Fast, Bottom-Up Heap Construction

← Older revision		Revision as of 03:11, 29 August 2017
Line 19:		Line 19:
	We can construct things faster, from O(N log N) to O(N), by utilizing a bottom-up construction process.		We can construct things faster, from O(N log N) to O(N), by utilizing a bottom-up construction process.

	Imagine that we are walking through an array of data, creating nodes for each element, and adding each node to ~~the heap. If we add~~ a ~~node to the last item in the tree, we have no information whatsoever about the last level of the~~ heap~~, so the node will definitely have to bubble up the node~~.		Imagine that we are walking through an array of data, creating nodes for each element, and adding each node to a heap.

	~~Contrast~~ that ~~with~~ the ~~situation of adding a node~~ to ~~the last position of a tree~~, ~~utilizing a bottom-~~up ~~construction process. Here~~, ~~we are adding~~ a ~~root~~ node ~~to an already-sorted subtree~~. This ~~invokes~~ the down ~~bubble algorithm~~.		If we follow the top-down heap construction, each item that we add to the heap will need to be downheap bubbled, and we could potentially end up downheap bubbling every single item, for a total cost of O(log N) per node, N nodes, for O(N log N). This is the top-down construction process.

	It is a subtle difference, but here's why this works: '''the maximum distance an element can possibly be moved is proportional to the distance from the insertion point to the point in the heap.''' If runtime is proportional to the sum of the heights, then for a heap with N nodes, this is O(N).		To improve on that, we can limit the distance that each node will downheap bubble by working our way from the bottom up. In this way, we know that all sub-heaps of the inserted node will already be heap-ordered.

			We don't want to begin with the LAST open position, because if we add a new node to the last open position, we know nothing whatsoever about the last level of the heap, and the node will definitely need to bubble up the heap - potentially the entire height of the tree.

			Instead, we want to add the new node to the root position of an already-sorted subtree. This invokes the downheap bubble algorithm, but we know that when we get several steps in, we are adding a new root node to a heap that is already heap-ordered.

			It is a subtle difference, but here's why this works: '''the maximum distance an element can possibly be moved is proportional to the distance from the insertion point to the point in the heap.''' This makes the runtime for a single insert O(1), because we don't have to bubble it all the way down. If runtime is proportional to the sum of the heights, then for a heap with N nodes, this is O(N).

	<pre>		<pre>

Admin: /* Fast, Bottom-Up Heap Construction */

2017-07-26T19:39:53Z

Fast, Bottom-Up Heap Construction

← Older revision		Revision as of 19:39, 26 July 2017
Line 18:		Line 18:

	We can construct things faster, from O(N log N) to O(N), by utilizing a bottom-up construction process.		We can construct things faster, from O(N log N) to O(N), by utilizing a bottom-up construction process.

			Imagine that we are walking through an array of data, creating nodes for each element, and adding each node to the heap. If we add a node to the last item in the tree, we have no information whatsoever about the last level of the heap, so the node will definitely have to bubble up the node.

			Contrast that with the situation of adding a node to the last position of a tree, utilizing a bottom-up construction process. Here, we are adding a root node to an already-sorted subtree. This invokes the down bubble algorithm.

			It is a subtle difference, but here's why this works: '''the maximum distance an element can possibly be moved is proportional to the distance from the insertion point to the point in the heap.''' If runtime is proportional to the sum of the heights, then for a heap with N nodes, this is O(N).

			<pre>
			public static<T> void makeHeap(T[] arr, Comparator<T> comp) {
			for(int i=arr.length/2; i>=0; i--) {
			percolateDown(arr, comp, arr.length, i);
			}
			}

			public static<T> void perclateDown(T[] arr, Comparator<T> comp, int heapSize, int i) {
			...
			}
			</pre>

	==Heap Sort Pseudocode==		==Heap Sort Pseudocode==

Admin: /* Heap Construction */

2017-07-26T19:34:14Z

Heap Construction

← Older revision		Revision as of 19:34, 26 July 2017
Line 3:		Line 3:
	Heaps are used in priority queues to keep items in a sorted order. But heaps are also useful for general sorting purposes. The heap sort algorithm starts by constructing a heap (tree data structure) and linking each heap node to a particular element in the original data. Once the heap is constructed, the algorithm removes items one at a time from the root node, and puts them in their final sorted position.		Heaps are used in priority queues to keep items in a sorted order. But heaps are also useful for general sorting purposes. The heap sort algorithm starts by constructing a heap (tree data structure) and linking each heap node to a particular element in the original data. Once the heap is constructed, the algorithm removes items one at a time from the root node, and puts them in their final sorted position.

	==Heap Construction==		==Top-Down Heap Construction==

	There are several ways to construct a heap. The "normal" or naive way is to ~~continually add nodes at~~ the ~~root. This bubbles nodes down~~ the ~~tree until they reach~~ the ~~correct final position~~.		There are several ways to construct a heap. The "normal" or naive way is to walk through the array of elements, adding each node to the last open position in the heap.

	This takes ~~about~~ O(N log N) time.		(Note that heaps fill in nodes in a left-to-right, top-to-bottom manner.)

			If we add an item to the last open position in a tree, and it is smaller than its parent, we simply swap that node with its parent.

			This takes O(N log N) time.

			However, we can improve the performance of this top-down construction process, by utilizing the fact that we are inserting a node into a sorted tree. This is still O(N log N), but in reality is more like O(N).

	==Fast, Bottom-Up Heap Construction==		==Fast, Bottom-Up Heap Construction==

Admin: /* Flags */

2017-07-26T19:31:45Z

Flags

← Older revision		Revision as of 19:31, 26 July 2017
Line 19:		Line 19:
	=Flags=		=Flags=

	{{~~PriorityQueueFlag~~}}		{{PriorityQueuesFlag}}

	{{TreesFlag}}		{{TreesFlag}}

Admin: /* Fast Heap Construction */

2017-07-26T19:31:38Z

Fast Heap Construction

← Older revision		Revision as of 19:31, 26 July 2017
Line 9:		Line 9:
	This takes about O(N log N) time.		This takes about O(N log N) time.

	==Fast Heap Construction==		==Fast, Bottom-Up Heap Construction==

	We can construct things faster by		We can construct things faster, from O(N log N) to O(N), by utilizing a bottom-up construction process.

	==Heap Sort Pseudocode==		==Heap Sort Pseudocode==

Admin: Created page with "Heaps are data structures with weak sorting - that is, the item at the root node is always guaranteed to be the minimum element, but the only invariant in a heap is that any c..."

2017-07-26T19:25:43Z

Created page with "Heaps are data structures with weak sorting - that is, the item at the root node is always guaranteed to be the minimum element, but the only invariant in a heap is that any c..."

New page

Heaps are data structures with weak sorting - that is, the item at the root node is always guaranteed to be the minimum element, but the only invariant in a heap is that any child node must be smaller than its parent.

Heaps are used in priority queues to keep items in a sorted order. But heaps are also useful for general sorting purposes. The heap sort algorithm starts by constructing a heap (tree data structure) and linking each heap node to a particular element in the original data. Once the heap is constructed, the algorithm removes items one at a time from the root node, and puts them in their final sorted position.

==Heap Construction==

There are several ways to construct a heap. The "normal" or naive way is to continually add nodes at the root. This bubbles nodes down the tree until they reach the correct final position.

This takes about O(N log N) time.

==Fast Heap Construction==

We can construct things faster by

==Heap Sort Pseudocode==

=Flags=

{{PriorityQueueFlag}}

{{TreesFlag}}

[[Category:Heaps]]
[[Category:Trees]]
[[Category:Sort]]
[[Category:Heap Sort]]