# Algorithm for Heap Insertion to Make New Node Rightmost Leaf

• MHB
• evinda
In summary, to rewrite the HeapInsert function to be conducted from top to bottom, you would need to traverse down the heap and compare the key of each node to its parent, swapping values if necessary. This would ensure that the new inserted node is the rightmost child of the last node of the second last level with a time complexity of $O(\log m)$ and the properties of a heap will still be maintained.
evinda
Gold Member
MHB
Hello and merry Christmas! (Happy)

Suppose that we have this heap:

View attachment 3745

Applying this algorithm:

Code:
HeapInsert(HeapTable A, int size, Key K, Type I) {
if (size == N) then error; /* Heap is full */
m = size;
while (m > 0 and K < Α[floor((m-1)/2)]->Key) {
Α[m]->key = Α[floor((m-1)/2)]->Key;
Α[m]->data = Α[floor((m-1)/2)]->data; /
}
Α[m]->Key = K;
Α[m]->data = I;
size++;
}

we will get the following:

View attachment 3746

I want to rewrite the function [m]HeapInsert[/m] so that it is conducted from top to bottom. Especially, the function should make appropriate swaps of keys while traversing nodes from the root to the node that will be the parent node of the new inserted node.
These actions should be done so that after the insertion, the new inserted node is the rightmost leaf and that no further actions( for example swaps) are needed after the placement of the new node at the array that implements the heap. The function should have time complexity $O(\log m)$ and it should keep the properties of a heap.
So, do we have to create a new node that is the rightmost child of the last node of the second last level and then compare its key with the key of its parent node and if it is smaller to swap their values and continue this procedure till we find a key that is smaller or until we reach the root? (Thinking)

#### Attachments

• heap4.png
4.2 KB · Views: 61
• heap4.png
5.7 KB · Views: 64
Yes, that is one way of rewriting the HeapInsert function. You would have to traverse down the heap (from the root node to the node that will be the parent of the new inserted node) and compare the key of each node to the key of its parent. If the key of the node is smaller than the key of its parent, you would have to swap their values. By following this approach, you will ensure that the new inserted node is the rightmost child of the last node of the second last level and no further actions are needed after the placement of the new node at the array that implements the heap. This approach will have a time complexity of $O(\log m)$ and the properties of a heap will still be preserved.

## 1. What is an algorithm for heap insertion to make a new node the rightmost leaf?

The algorithm for heap insertion to make a new node the rightmost leaf involves the following steps:

• 1. Starting from the root node, traverse the heap to find the last level and rightmost node.
• 2. If the last level is not completely filled, insert the new node at the next available position.
• 3. If the last level is completely filled, insert the new node as the left child of the rightmost node.
• 4. Compare the new node with its parent and swap if it is smaller (for a min heap) or larger (for a max heap).
• 5. Repeat the comparison and swapping process until the new node is in the correct position in the heap.

## 2. Why is it important to make the new node the rightmost leaf in a heap?

Making the new node the rightmost leaf in a heap ensures that the heap maintains the property of completeness. This means that all levels of the heap are filled except possibly the last level, which is filled from left to right. This property is important for maintaining the efficiency of heap operations.

## 3. What is the time complexity of the algorithm for heap insertion to make a new node the rightmost leaf?

The time complexity of the algorithm for heap insertion to make a new node the rightmost leaf is O(log n), where n is the number of nodes in the heap. This is because the algorithm involves traversing the heap to find the last level, which takes O(log n) time, and then swapping the new node with its parent, which takes O(log n) time at worst. Therefore, the overall time complexity is O(log n).

## 4. Can the algorithm for heap insertion to make a new node the rightmost leaf be used for both min and max heaps?

Yes, the algorithm for heap insertion to make a new node the rightmost leaf can be used for both min and max heaps. The only difference is in the comparison and swapping step, where the new node is compared with its parent and swapped if it is smaller for a min heap, and larger for a max heap.

## 5. Is the algorithm for heap insertion to make a new node the rightmost leaf stable?

Yes, the algorithm for heap insertion to make a new node the rightmost leaf is stable. This means that the relative order of nodes with equal key values is preserved after insertion. This is because the algorithm only compares and swaps the new node with its parent, and does not change the position of other nodes in the heap.

• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
3
Views
1K
• Programming and Computer Science
Replies
1
Views
2K
• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
5
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Programming and Computer Science
Replies
1
Views
2K
• General Math
Replies
6
Views
1K
• Engineering and Comp Sci Homework Help
Replies
2
Views
3K