Heap - Revision history

Savoundg at 05:22, 3 October 2020

2020-10-03T05:22:00Z

← Older revision		Revision as of 05:22, 3 October 2020
Line 10:		Line 10:
	* right: index x 2 + 2		* right: index x 2 + 2

	==== Insertion ====		==== Insertion O(log n) ====
	Insert the new element at the leaves and bubble it up ~~in O(log n)~~. Or, we can replace the min. element with the new element and bubble it down.		Insert the new element at the leaves and bubble it up. Or, we can replace the min. element with the new element and bubble it down.

	==== Extract min. element ====		==== Extract min. element O(log n) ====
	The min. element of min. Heap is the root. To remove it, swap with the bottom-most right-most element and bubble it down, swapping with the smaller element.		The min. element of min. Heap is the root. To remove it, swap with the bottom-most right-most element and bubble it down, swapping with the smaller element.

Savoundg at 05:19, 3 October 2020

2020-10-03T05:19:49Z

← Older revision		Revision as of 05:19, 3 October 2020
Line 10:		Line 10:
	* right: index x 2 + 2		* right: index x 2 + 2

	=== Insertion ===		==== Insertion ====
	Insert the new element at the leaves and bubble it up. Or, we can replace the min. element with the new element and bubble it down.		Insert the new element at the leaves and bubble it up in O(log n). Or, we can replace the min. element with the new element and bubble it down.

			==== Extract min. element ====
			The min. element of min. Heap is the root. To remove it, swap with the bottom-most right-most element and bubble it down, swapping with the smaller element.

	== Resources ==		== Resources ==

Savoundg at 05:12, 3 October 2020

2020-10-03T05:12:41Z

← Older revision		Revision as of 05:12, 3 October 2020
Line 1:		Line 1:
	A Heap is a binary tree. It has two forms: min. Heap and max. Heap.		A Heap is a complete binary tree. It has two forms: min. Heap and max. Heap.

	In a min. Heap, the root of any sub-tree is smaller than its children. The deeper we go into the children, the bigger they are. The minimum element is the root of the heap.		In a min. Heap, the root of any sub-tree is smaller than its children. The deeper we go into the children, the bigger they are. The minimum element is the root of the heap.

Savoundg at 07:01, 3 June 2018

2018-06-03T07:01:17Z

← Older revision		Revision as of 07:01, 3 June 2018
Line 11:		Line 11:

	=== Insertion ===		=== Insertion ===
	Insert the new element at the leaves and bubble it up.		Insert the new element at the leaves and bubble it up. Or, we can replace the min. element with the new element and bubble it down.

	== Resources ==		== Resources ==

Savoundg at 06:57, 3 June 2018

2018-06-03T06:57:03Z

← Older revision		Revision as of 06:57, 3 June 2018
Line 11:		Line 11:

	=== Insertion ===		=== Insertion ===
	Insert the new element at the leaves and bubble ~~them~~ up.		Insert the new element at the leaves and bubble it up.

	== Resources ==		== Resources ==

Savoundg: Created page with "A Heap is a binary tree. It has two forms: min. Heap and max. Heap. In a min. Heap, the root of any sub-tree is smaller than its children. The deeper we go into the children,..."

2018-06-03T06:49:38Z

Created page with "A Heap is a binary tree. It has two forms: min. Heap and max. Heap. In a min. Heap, the root of any sub-tree is smaller than its children. The deeper we go into the children,..."

New page

A Heap is a binary tree. It has two forms: min. Heap and max. Heap.

In a min. Heap, the root of any sub-tree is smaller than its children. The deeper we go into the children, the bigger they are. The minimum element is the root of the heap.

In a max. Heap, the root of any-sub tree is bigger than its children. The deeper we go into the children, the smaller they are. The maximum element is the root of the heap.

A heap can be implemented in a array using a simple mapping:
* get parent: (index - 2) / 2
* left: index x 2 + 1
* right: index x 2 + 2

=== Insertion ===
Insert the new element at the leaves and bubble them up.

== Resources ==
{| class="wikitable"
!
|-
|https://www.youtube.com/watch?v=oSWTXtMglKE
|}