You're required to devise a data structure as follows:
- It is a complete binary tree
- The key of each node is larger than its children's (if it has any)
We call it Heap. Initially your heap is empty, then you are asked to insert \(N\) distinct integers into the heap one by one.
When you insert a new element into the heap, you should:
- Place it at the leftmost position of the complete binary tree
- Swap it with its father if it is larger than the key of its father until it becomes the root of the heap or it is smaller than the key of its father
Now little HEAP wants to know the number of swapping times in each insertion.