Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- using namespace std;
- ifstream fin;
- ofstream fout;
- struct sValue{
- sValue(int k, int v)
- {
- key = k; data = v;
- };
- int key;
- int data;
- };
- void quickSort(vector<sValue> &a, int l, int r);
- int leftChild(int i);
- int rightChild(int i);
- int parent(int i);
- void insert(vector<sValue> &heap, sValue value, int &N);
- void heapify(vector<sValue>& heap, int i, int type);
- sValue extract(vector<sValue> &heap, int &N);
- int main()
- {
- fin.open("input.txt", ios_base::in);
- fout.open("output.txt", ios_base::out);
- int N, M, tmp,
- count = 0;
- fin >> N >> M;
- int countIn = N;
- vector<sValue> heap;
- for (int i = 0; i < N; i++)
- {
- fin >> tmp;
- insert(heap, sValue(i, tmp), count);
- }
- heapify(heap, 0, 1);
- for (int i = 0; i < M; i++)
- {
- sValue left = extract(heap,count),
- right = extract(heap,count);
- tmp = left.data + right.data;
- insert(heap, sValue(++countIn, tmp), count);
- }
- quickSort(heap, 0, heap.size() - 1);
- for (int i = 0; i < heap.size(); i++)
- fout << heap[i].data << " ";
- fin.close();
- fout.close();
- return 0;
- }
- int leftChild(int i)
- {
- return 2 * i + 1;
- }
- int rightChild(int i)
- {
- return 2 * i + 2;
- }
- int parent(int i)
- {
- return (i-1) / 2;
- }
- void quickSort(vector<sValue> &heap, int l, int r)
- {
- int x = heap[(l+r) / 2].key;
- int left = l;
- int right = r;
- while (left <= right)
- {
- for (;heap[left].key < x; left++);
- for (;heap[right].key > x; right--);
- if (left <= right)
- swap(heap[left++], heap[right--]);
- }
- if (l < right)
- quickSort(heap, l, right);
- if (left < r)
- quickSort(heap, left, r);
- }
- void heapify(vector<sValue>& heap, int i, int type)
- {
- int l,r,largest;
- while (true)
- {
- l = leftChild(i);
- r = rightChild(i);
- largest = i;
- if (type)
- {
- if(l < heap.size() && heap[l].data == heap[largest].data && heap[l].key < heap[largest].key)
- largest = l;
- if(r < heap.size() && heap[r].data == heap[largest].data && heap[r].key < heap[largest].key)
- largest = r;
- }
- else
- {
- if(l < heap.size() && heap[l].data < heap[largest].data)
- largest = l;
- if(r < heap.size() && heap[r].data < heap[largest].data)
- largest = r;
- }
- if (largest == i)
- break;
- swap(heap[i], heap[largest]);
- i = largest;
- }
- }
- sValue extract(vector<sValue> &heap, int &N)
- {
- N--;
- sValue result = heap[0];
- heap[0] = heap[N];
- heap.pop_back();
- for (int i = 0; i < 2; i++)
- heapify(heap, 0, i);
- return result;
- }
- void insert(vector<sValue> &heap, sValue value, int &N)
- {
- int i = N,
- p = parent(i);
- heap.push_back(value);
- for (;p >= 0, i > 0; i = p, p = parent(i))
- if(heap[i].data < heap[p].data)
- swap(heap[i],heap[p]);
- N++;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement