Number of swaps performed by Heapify
Given an initially empty heap, you are asked to perform
qqueries. There are 2 types of queries:
add x- should add
xto the heap
pop- should delete the root of the heap
For each of the queries, you are asked to print the number of swaps needed to restructure the heap to make it satisfy the max-heap property.
popoperations, the swapping of the root and the last element is also counted as a swap.
The first line of the input contains a single integer
qlines contain queries - each on a separate line. It’s guaranteed that for all
addqueries the value of
xdoes not exceed in absolute value.
The program should print the number of swap operations each on a separate line.
7 add 1 add 2 add -3 add 4 pop add -2 pop
0 1 0 2 2 0 2
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB