Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "stdafx.h"
- #include<iostream>
- #include<vector>
- #include<string>
- using namespace std;
- vector<int> heap;
- vector<int> heapmax;
- void siftUp(int v) {
- if (v == 0) return;
- int p = (v - 1) / 2; //родитель
- if (heap[v] < heap[p]) {
- swap(heap[v], heap[p]);
- siftUp(p);
- }
- }
- void siftDown(int v) {
- int left = 2 * v + 1;
- int right = 2 * v + 2;
- if (left >= heap.size()) return;
- if (left == heap.size() - 1) right = left;
- int imax = heap[left] < heap[right] ? left : right;
- if (heap[v] > heap[imax]) {
- swap(heap[v], heap[imax]);
- siftDown(imax);
- }
- }
- void siftUpMax(int v) {
- if (v == 0) return;
- int p = (v - 1) / 2; //родитель
- if (heapmax[v] > heapmax[p])
- {
- swap(heapmax[v], heapmax[p]);
- siftUpMax(p);
- }
- }
- void siftDownMax(int v)
- {
- int left = 2 * v + 1;
- int right = 2 * v + 2;
- if (left >= heapmax.size()) return;
- if (left == heapmax.size() - 1) right = left;
- int imax = heapmax[left] > heapmax[right] ? left : right;
- if (heapmax[v] < heapmax[imax])
- {
- swap(heapmax[v], heapmax[imax]);
- siftDownMax(imax);
- }
- }
- int main() {
- setlocale(LC_CTYPE, "rus");
- string str;
- cout << "ADD <number> - добавляет новый элемент в heap и heapmax\nMIN - выводит минимальный элемент из heap" << endl
- << "MAX - выводит максимальный элемент из heapmax\nCLEAR - очищает heap и heapmax" << endl;
- while (cin >> str) {
- if (str == "ADD") {
- int x = 0;
- cin >> x;
- heap.push_back(x);
- siftUp(heap.size() - 1);
- heapmax.push_back(x);
- siftUpMax(heapmax.size() - 1);
- }
- else if (str == "MIN") {
- if (!heap.empty()) {
- cout << heap[0] << '\n';
- heap[0] = heap.back();
- heap.pop_back();
- siftDown(0);
- }
- else {
- cout << "NO\n";
- }
- }
- else if (str == "MAX")
- {
- if (!heap.empty())
- {
- cout << heapmax[0] << '\n';
- heapmax[0] = heapmax.back();
- heapmax.pop_back();
- siftDownMax(0);
- }
- else
- {
- cout << "NO\n";
- }
- }
- else if (str == "CLEAR") {
- heap = vector<int>();
- heapmax = vector<int>();
- }
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment