- #1

evinda

Gold Member

MHB

- 3,836

- 0

Hello and merry Christmas! (Happy)

Suppose that we have this heap:

View attachment 3745

Applying this algorithm:

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)

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)