Binary Heap

AlgoDS/DataStructure 2020. 1. 16. 12:46

1. Overview

Basically, the idea is that the heap gets filled from the top to the bottom of the fill the top node first and then you build the left child and then you build the right child and then the next note if you want to add it to this heap you basically put it to the left and then to the right and then you put the love child and then the right child. So basically you build it on the way down as well as from the left to the right.

2. Characteristic

If we're going to implement heap in code is either using a linked list or an array. The arrays are a very basic data structure used to store a collection of items right. So the way this is typically done is using an array and that's the best approach of doing this. The relationship between these parents and these children in an array data structure. So going to translate this map so to speak of these relationships of a parent. And then it's two children and an array.

Parent: Floor($\frac{n-1}{2}$)
Left Children: 2n + 1
Right Children: 2n + 2

2. Types of Heap

2.1 Max Heap

In the case of a max heap, at the root is the largest element in the entire heap.

Why is a smaller element to the right number in the heap data structure? all that matters is the children better be smaller than their parents.

2.2 Min Heap

In the Min heap, the root is the smallest element in the entire heap and all parents have you know for

2.3 Insert element

New element 3 is inserted last right spot in heap.

After that, bubble it up until it gets to the right spot which is left child of the root which is 2.

2.4 Deleting element

If 2 is removed. That's just how typically the data structure is implemented when needed to remove elements you basically remove the root.

Then the last element replaces that empty spot.

After that, the element might not be the right spot.

So the step that's required here is to compare both of its children and see which one is the smaller one in Min heap. If it is Max heap, the right one is a bigger one. Buble it down until heap stores it properly.