1 Convert array into heap

Problem Introduction

In this problem you will convert an array of integers into a heap. This is the crucial step of the sorting

algorithm called HeapSort. It has guaranteed worst-case running time of ( log ) as opposed to QuickSorts

average running time of ( log ). QuickSort is usually used in practice, because typically it is faster, but

HeapSort is used for external sort when you need to sort huge files that dont fit into memory of your

computer.

Problem Description

Task. The first step of the HeapSort algorithm is to create a heap from the array you want to sort. By the

way, did you know that algorithms based on Heaps are widely used for external sort, when you need

to sort huge files that dont fit into memory of a computer?

Your task is to implement this first step and convert a given array of integers into a heap. You will

do that by applying a certain number of swaps to the array. Swap is an operation which exchanges

elements and of the array for some and . You will need to convert the array into a heap using

only () swaps, as was described in the lectures. Note that you will need to use a min-heap instead

of a max-heap in this problem.

Input Format. The first line of the input contains single integer . The next line contains space-separated

integers .

Constraints. 1 100 000; 0 , 1; 0 0, 1, . . . , 1 109. All are distinct.

Output Format. The first line of the output should contain single integer the total number of swaps.

must satisfy conditions 0 4. The next lines should contain the swap operations used

to convert the array into a heap. Each swap is described by a pair of integers , the 0-based

indices of the elements to be swapped. After applying all the swaps in the specified order the array

must become a heap, that is, for each where 0 1 the following conditions must be true:

1. If 2 + 1 1, then < 2+1.

2. If 2 + 2 1, then < 2+2.

Note that all the elements of the input array are distinct. Note that any sequence of swaps that has

length at most 4 and after which your initial array becomes a correct heap will be graded as correct.

Time Limits. C: 1 sec, C++: 1 sec, Java: 3 sec, Python: 3 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3

sec, Ruby: 3 sec, Scala: 3 sec.

Memory Limit. 512MB.

Sample 1.

Input:

5

5 4 3 2 1

Output:

3

1 4

0 1

1 3

After swapping elements 4 in position 1 and 1 in position 4 the array becomes 5 1 3 2 4.

After swapping elements 5 in position 0 and 1 in position 1 the array becomes 1 5 3 2 4.

After swapping elements 5 in position 1 and 2 in position 3 the array becomes 1 2 3 5 4, which is

already a heap, because 0 = 1 < 2 = 1, 0 = 1 < 3 = 2, 1 = 2 < 5 = 3, 1 = 2 < 4 = 4.

Sample 2.

Input:

5

1 2 3 4 5

Output:

0

The input array is already a heap, because it is sorted in increasing order.

********SOURCE CODE***********

#include

#include

#include

using std::vector;

using std::cin;

using std::cout;

using std::swap;

using std::pair;

using std::make_pair;

class HeapBuilder {

private:

vector data_;

vector< pair > swaps_;

void WriteResponse() const {

cout << swaps_.size() << " ";

for (int i = 0; i < swaps_.size(); ++i) {

cout << swaps_[i].first << " " << swaps_[i].second << " ";

}

}

void ReadData() {

int n;

cin >> n;

data_.resize(n);

for(int i = 0; i < n; ++i)

cin >> data_[i];

}

void GenerateSwaps() {

swaps_.clear();

// The following naive implementation just sorts

// the given sequence using selection sort algorithm

// and saves the resulting sequence of swaps.

// This turns the given array into a heap,

// but in the worst case gives a quadratic number of swaps.

//

// TODO: replace by a more efficient implementation

for (int i = 0; i < data_.size(); ++i)

for (int j = i + 1; j < data_.size(); ++j) {

if (data_[i] > data_[j]) {

swap(data_[i], data_[j]);

swaps_.push_back(make_pair(i, j));

}

}

}

public:

void Solve() {

ReadData();

GenerateSwaps();

WriteResponse();

}

};

int main() {

std::ios_base::sync_with_stdio(false);

HeapBuilder heap_builder;

heap_builder.Solve();

return 0;

}