Heap - Min e Max

Heap - Min Heap

Heap is a more efficient version of the priority list. Take into account the insertion and removal methods of the Priority Queue Sorted and Unsorted, in Unsorted insertion costs O(1), removing costs O(n), while Sorted insertion costs O(n) and removing O(1).

	sorted	unsorted
insert	O(n)	O(1)
remove	O(1)	O(n)

Heap is built by an Array, but its representation is a binary tree, the element with the most priority is at the top, the root. It is filled from top to bottom and right to left, with no children missing!

?

However, there is the possibility of building the data structure with the highest priority being defined by the highest key value. In this case we have the max heap, which we will see later.

Min_Heap

To be a valid Heap, all child elements must have lower or equal priority than their parents. Furthermore, it must be complete with no missing children, otherwise the array will have a blank space.

?

A more formal way of carrying out this definition is to say that a binary tree is complete if its levels 0, 1, 2, · · · h − 1 have the maximum possible elements and the elements existing at level h are allocated as far left as possible.

As mentioned, heap is made up of an array (represented in green), but can be viewed as a tree structure, as shown in the image below.

There are two ways to assemble the Heap, with the first element in position 0, or without position 0, in this article we will see the difference between the two cases. The elements at the top always have their children, commonly known as elements at the bottom, to discover these children, in the case of index 0, you can get this information using these calculations:

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

If you use a version with 0 not filled in, just reduce the sum, that is, 1-1=0, in the parent case it is index / 2.

Insert

It is always added at the end, the only concern you should have is when checking whether the child element has a lower key than the parent, for this purpose bubbling up is performed, which is when the Keys of the inserted element are compared and the father, changing if necessary.

Speaking in more detail, place the element in the last empty space of the tree and, as you need to compare its key with that of the parent, we need to calculate the parent's index to access its key. To find out the father, use the calculation mentioned:

parent = (indexDoFilho -1)/2

And for this, the indexDoFilho is missing: to obtain this, we take a variable to be the current index, as we are in the insert which is an addition at the end, the current index is the last one, being:

currentIndex = size-1

Now having the current index, call Parent and find out who is the father of the element being inserted. We want the parent of this new element because, to organize the tree correctly, this element must be compared with its parent and, if its key is smaller, they must swap locations.

As long as the current index is greater than 0 (in order to avoid picking up an unavailable index) and the current index is smaller than the parent's index, if this condition is true, the element needs to be exchanged with the parent to guarantee ownership of the minimum heap and then the swap occurs and then the current index receives the parent's index, and then takes the parent's parent (KKKKK) for . Swap is a method that uses the structure of a normal exchange of values.

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

Being related:

parent = (indexDoFilho -1)/2

Swap being a normal method of exchanging values:

currentIndex = size-1

If the value of the current (child) element is less than the value of the parent, this indicates that the minimum heap property has been violated. In a minimal heap, the parent must always be less than or equal to the child. When this condition is not met, the child must swap places with the parent so that the smaller value continues to "climb" in the heap until it finds the correct position, where the property will be maintained.

Remove

Removes the index 0 element, but the tree is no longer complete! To solve this, pull the last element of the array to the beginning, that is, the last element that was added goes to the top of the tree. After that, check again, but now from top to bottom. In other words, now is the time to compare parents with their children! (sinkdown)
The sinkDown() method moves the element down (or “sinks”) in the heap, until it is in the correct position, where its value is less than or equal to that of its children (if it is in a position with children).
In sinkDown there is a variable to store the index of the element with the lowest key starting at the root and another for the current index. Then, a loop that will last until the index of the current element is equal to the index of the element with the lowest key. Inside the loop, get the children of the current one and see if the children are within the array range and if the child's index is less than the minimum index, it updates the minimum.

public void insert(K key, V value) { //o(log n)
    if (isFull()){
        throw new RuntimeException("full");
    }
    //adc a entry na ultima posição do vetor
    heap[size++]=new PriorityEntry(key, value);
    //guarda o index que esse novo elemento tá
    int currentIndex = size-1;
    //chama o método parent pra calcular quem é o pai do novo elemento
    int parent = parent(currentIndex);
    //percorre enquanto o index nao for o 0 e o index ser 
    while (currentIndex>0 && compare(currentIndex, parent)<0){
        swap(currentIndex, parent);
        currentIndex = parent;
        parent = parent(currentIndex);
    }
}

In this case:

protected int parent(int index){
        return (index-1)/2;
}

Summary:

Min Heap Properties:

• Complete binary tree structure.
• The parent node always has a value equal to or less than its child nodes.
• Implemented via array, where the position of the children and parent is determined by formulas based on the index.

To calculate positions of children and parents:

• Left: leftChild = index * 2 1
• Right: rightChild = index * 2 2
• Parent: parent = (index - 1) / 2

Version without index 0: Just subtract 1 from the calculations, resulting in:

• leftChild = index * 2
• rightChild = index * 2 1
• parent = index / 2

Heap - Max Heap

The highest value is at the root, so the parent node has the same or greater value than its children

The formulas for calculating children and parents:

• Left: leftChild = index * 2 1
• Right: rightChild = index * 2 2
• Parent: parent = (index - 1) / 2

Insert

Adds the element at the end and bubbling up, which would be comparing the element with its parent, changing location if necessary. O(log n).

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

Remove

Removes the heapMax[0] element, aka the root, and then takes the last element and moves it up to the root, calling sinkdown then pushing the new element from the root down until it finds its correct position.

sinkDown needs to ensure that the value in the parent node is greater than or equal to the values ​​in the child nodes. Therefore, when sinking a node, it will be compared with the largest child.

In the Min Heap, sinkDown must ensure that the value in the parent node is less than or equal to the values ​​of the children. In this case, the comparison is made with the smallest child.

parent = (indexDoFilho -1)/2

currentIndex = size-1

Differences

• In Max Heap, sinkDown needs to ensure that the value in the parent node is greater than or equal to the values ​​in the child nodes. Therefore, when sinking a node, it will be compared with the largest child.
• In Max Heap, if the parent node is smaller than the largest of its children, then it must swap with the largest child to ensure that the largest value is as high as possible.
• In the Min Heap, sinkDown must ensure that the value in the parent node is less than or equal to the values ​​of the children. In this case, the comparison is made with the smallest child.
• In the Min Heap, switching occurs if the parent node is greater than the smallest of the children, keeping the smallest value at the top

The above is the detailed content of Heap - Min e Max. For more information, please follow other related articles on the PHP Chinese website!