Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- using namespace std;
- int GetParent (int index) {
- return (index - 1) / 2;
- }
- int Left (int index) {
- return 2 * index + 1;
- }
- int Right (int index) {
- return 2 * index + 2;
- }
- template <class T>
- T Get_max (T* heap) {
- return heap[0];
- }
- template <class T>
- void SiftUp (T* heap, int heap_size, int index) {
- if (index <= 0) {
- return;
- }
- else if (heap[index] > heap[GetParent(index)]) {
- swap(heap[index], heap[GetParent(index)]);
- SiftUp(heap, heap_size, GetParent(index));
- }
- }
- template <class T>
- void SiftDown (T* heap, int heap_size, int index) {
- int min_index = index;
- if (2 * index + 1 < heap_size && heap[min_index] < heap[Left(index)]) {
- min_index = Left(index);
- }
- if (2 * index + 2 < heap_size && heap[min_index] < heap[Right(index)]) {
- min_index = Right(index);
- }
- swap(heap[index], heap[min_index]);
- if (min_index != index) {
- SiftDown(heap, heap_size, min_index);
- }
- }
- template <class T>
- void Insert (T* heap, int& heap_size, T value, T start_index) {
- ++heap_size;
- int begin = 0;
- for (int i = start_index; i < heap_size; ++i) {
- if (value < heap[i]) {
- begin = i;
- break;
- }
- if (i == heap_size - 1) {
- begin = heap_size - 1;
- }
- }
- for (int i = heap_size - 2; i > begin - 1; --i) {
- heap[i + 1] = heap[i];
- }
- heap[begin] = value;
- }
- template <class T>
- void ExtractMin (T* heap, int& heap_size) {
- swap(heap[0], heap[heap_size - 1]);
- --heap_size;
- SiftDown(heap, heap_size, 0);
- }
- template <typename T>
- void BuildHeap (T* heap, int heap_size) {
- for (int i = heap_size / 2 - 1; i >= 0; --i) {
- SiftDown(heap, heap_size, i);
- }
- }
- template <typename T>
- void HeapSort (T* heap, T heap_size) {
- BuildHeap(heap, heap_size);
- while (heap_size > 0) {
- ExtractMin(heap, heap_size);
- }
- }
- template <typename T>
- void RemoveHeap (T* heap, T& heap_size) {
- for (int i = 0; i < heap_size - 2; ++i) {
- heap[i] = heap[i + 2];
- }
- heap_size -= 2;
- }
- int main() {
- int heap_size;
- cin >> heap_size;
- int* heap = new int[2 * heap_size + 1];
- double total_sum = 0;
- for (int i = 0; i < heap_size; ++i) {
- cin >> heap[i];
- }
- int start_index = 0;
- int size_of_first_heap = heap_size;
- HeapSort(heap, heap_size);
- for (int i = 0; i < size_of_first_heap - 1; ++i) {
- int current_sum = heap[2 * i] + heap[2 * i + 1];
- heap[2 * i] = -1;
- heap[2 * i + 1] = -1;
- total_sum += current_sum;
- start_index += 1;
- Insert(heap, heap_size, current_sum, start_index);
- }
- cout << fixed;
- cout << setprecision(2) << total_sum * 0.05;
- delete [] heap;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement