# 11216: 【原1216】heap

### 题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1216

## Description

insert x，将优先级值为x的元素入队

find x，找出优先级值大于x的最小的元素，输出其下标。如果有多个元素优先级值相同输出下标最小的那个。

DECREASE i v，将第i个节点的优先级值减少v。

## Sample Input1

``````9
insert 5
insert 6
insert 7
find 5
find 6
decrease 1 3
decrease 2 5
decrease 3 5
find 1
``````

## Sample Output1

``````2
3
2
``````

## Limit

find操作只要求时间复杂度O(n)，其他操作要求O(logn)

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/4/14.
//

#ifndef SBL_BPRIORITYQUEUE_H
#define SBL_BPRIORITYQUEUE_H

namespace bpq {
template<typename Item>
struct greater {
bool operator()(const Item &a, const Item &b) {
return a > b;
}
};

template<typename Item>
struct less {
bool operator()(const Item &a, const Item &b) {
return a < b;
}
};
}

template<typename Item, typename Comparator = bpq::greater<Item>>
class BPriorityQueue {
Comparator comparator;
Item *pq;
int N = 0;
int maxN;

private:
bool cmp(int i, int j) {
return comparator(pq[i], pq[j]);
}

void exch(int i, int j) {
Item item = pq[i];
pq[i] = pq[j];
pq[j] = item;
}

void resize(int newMaxN) {
Item *old = pq;
pq = new Item[newMaxN + 1];
int length = newMaxN > maxN ? maxN : newMaxN;
for (int i = 1; i <= length; ++i) {
pq[i] = old[i];
}
delete[] old;
}

void swim(int k) {
while (k > 1 && cmp(k, k / 2)) {
exch(k / 2, k);
k /= 2;
}
}

void sink(int k) {
int j;
while (2 * k <= N) {
j = 2 * k;
j += (j < N && cmp(j + 1, j));
if (cmp(j, k)) {
exch(k, j);
k = j;
} else break;
}
}

public:
BPriorityQueue() {
this->maxN = 1;
pq = new Item[1 + 1];
}

BPriorityQueue(int maxN) {
this->maxN = maxN;
pq = new Item[maxN + 1];
}

BPriorityQueue(const Item *pq, int size) {
maxN = N = size;
this->pq = new Item[size + 1];
for (int i = 1; i <= N; ++i) {
this->pq[i] = pq[i - 1];
}
for (int k = N / 2; k >= 1; --k) {
sink(k);
}
}

bool isEmpty() {
return N == 0;
}

int size() {
return N;
}

void insert(const Item &item) {
if (N == maxN)
resize(2 * N);
pq[++N] = item;
swim(N);
}

Item pop() {
if (N <= maxN / 4)
resize(maxN / 2);
Item item = pq[1];
exch(1, N);
--N;
sink(1);
return item;
}

const Item &peek() {
return pq[1];
}

int find(int x) {
int num = 0x7fffffff;
int ans;
for (int i = 1; i <= N; ++i) {
if (pq[i] > x && pq[i] < num) {
num = pq[i];
ans = i;
}
}
return ans;
}

void decrease(int i, const Item &v) {
pq[i] -= v;
swim(i);
}

virtual ~BPriorityQueue() {
delete[] pq;
}
};

#endif //SBL_BPRIORITYQUEUE_H

#include <iostream>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
BPriorityQueue<int, bpq::less<int>> pq(N);
char cmd[10];
int tmp, tmp2;
while (N--) {
cin >> cmd;
switch (cmd[0]) {
case 'i':
cin >> tmp;
pq.insert(tmp);
break;
case 'f':
cin >> tmp;
cout << pq.find(tmp) << '\n';
break;
case 'd':
cin >> tmp >> tmp2;
pq.decrease(tmp, tmp2);
break;
}
}
cout << endl;
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

constexpr int inf = 1e8;

int mmin(int a, int b) {
return a < b ? a : b;
}

template <class T>
class mVector {
T** vector_data = nullptr;
unsigned int size = 0;
unsigned int capacity = 0;

public:
//构造函数
mVector() = default;
mVector(unsigned int _size) :size(_size) {
capacity = _size * 2;
vector_data = new T * [capacity] {nullptr};
}
mVector(unsigned int _size, const T& val) :size(_size) {
capacity = _size * 2;
vector_data = new T * [capacity] {nullptr};
for (unsigned int i = 0; i < _size; ++i)
vector_data[i] = new T(val);
}
mVector(const mVector<T> & _vector) :size(_vector.size), capacity(_vector.capacity) {
vector_data = new T * [capacity] {nullptr};
for (int i = 0; i < size; ++i)
vector_data[i] = new T(*_vector.vector_data[i]);
}
//析构函数
~mVector() {
for (unsigned int i = 0; i < size; ++i)
delete vector_data[i];
delete[] vector_data;
}

//迭代器
class iterator {
T** pos = nullptr;
friend iterator mVector<T>::begin();
friend iterator mVector<T>::end();
friend void mVector<T>::erase(const iterator& val);
public:
iterator() = default;
iterator(const iterator& other) {
pos = other.pos;
}
iterator& operator++() {
++pos;
return *this;
}
iterator operator++(int) {
iterator temp(*this);
++pos;
return temp;
}
iterator& operator--() {
--pos;
return *this;
}
iterator operator--(int) {
iterator temp(*this);
--pos;
return temp;
}
bool operator==(const iterator& other) const {
return pos == other.pos;
}
bool operator!=(const iterator& other) const {
return pos != other.pos;
}
iterator& operator=(const iterator& other) {
pos = other.pos;
return *this;
}
T& operator*() const {
return **pos;
}
};

//增加元素
void push_back(const T & val) {
if (size < capacity)
vector_data[size++] = new T(val);
else {
T** temp_data = new T * [(capacity + 1) * 2]{ nullptr };
for (unsigned int i = 0; i < size; ++i)
temp_data[i] = vector_data[i];
temp_data[size++] = new T(val);
capacity = (capacity + 1) * 2;
delete[] vector_data;
vector_data = temp_data;
}
}

//删除末尾
void pop_back() {
delete vector_data[size];
vector_data[size--] = nullptr;
}

//清空
void clear() {
for (unsigned int i = 0; i < size; ++i) {
delete vector_data[i];
vector_data[i] = nullptr;
}
size = 0;
}

//删除
void erase(const iterator & val) {
delete* val.pos;
for (auto p = val.pos; p != vector_data + size - 1; ++p)
* p = *(p + 1);
--size;
vector_data[size] = nullptr;
}

//重载运算符
T & operator[](const unsigned int& pos) {
return *vector_data[pos];
}

iterator begin() {
iterator temp;
temp.pos = vector_data;
return temp;
}

iterator end() {
iterator temp;
temp.pos = vector_data + size;
return temp;
}

};

template <class T>
class myPriorityQueue {
public:
mVector<T> queueData;
unsigned int sizeOfQueue = 0;
bool(*cmp)(T a, T b) = [](T a, T b) {return a < b; };

//向下过滤
void percolateDown(unsigned int pos) {
while (pos * 2 <= sizeOfQueue) {
if (pos * 2 + 1 > sizeOfQueue) {
//交换
if (cmp(queueData[pos * 2], queueData[pos])) {
auto temp = queueData[pos * 2];
queueData[pos * 2] = queueData[pos];
queueData[pos] = temp;
}
break;
}
else {
bool minNum = cmp(queueData[pos * 2 + 1], queueData[pos * 2]);
if (cmp(queueData[pos * 2 + minNum], queueData[pos])) {
auto temp = queueData[pos * 2 + minNum];
queueData[pos * 2 + minNum] = queueData[pos];
queueData[pos] = temp;
pos = pos * 2 + minNum;
}
else break;
}
}
}

//构建
myPriorityQueue() {
queueData.clear();
queueData.push_back((T)0);
sizeOfQueue = 0;
}

//compare函数返回父结点a与孩子结点b的关系正确与否
myPriorityQueue(bool(*compare)(T a, T b)) :cmp(compare) {
queueData.clear();
queueData.push_back(*new T);
sizeOfQueue = 0;
}

//根据数组建立堆
void buildHeap(T* eleData, unsigned int eleNum) {
queueData.clear();
sizeOfQueue = eleNum;
queueData.push_back(*new T);
for (unsigned int i = 1; i <= eleNum; i++)
queueData.push_back(eleData[i - 1]);
//向下过滤
for (unsigned int pos = eleNum / 2; pos > 0; pos--)
percolateDown(pos);
}

void refresh() {
//向下过滤
for (unsigned int pos = size() / 2; pos > 0; pos--)
percolateDown(pos);
}

//判断是否空
bool empty() {
return sizeOfQueue == 0;
}

//返回队列大小
auto size() {
return sizeOfQueue;
}

//入队
void push(const T & input) {
sizeOfQueue++;
queueData.push_back(input);

//向上过滤
for (auto i = sizeOfQueue; i > 1; i = i / 2) {
//判断是否比父结点更小
if (cmp(queueData[i], queueData[i / 2])) {
//交换
auto temp = queueData[i];
queueData[i] = queueData[i / 2];
queueData[i / 2] = temp;
}
else break;
}
}

//队列最前
T top() {
return queueData[1];
}

//出队
T pop() {
auto temp = queueData[1];
queueData[1] = queueData[sizeOfQueue--];
queueData.pop_back();
percolateDown(1);
return temp;
}
};

int find(int num,int startPos,int& pos,int numSize,mVector<int> &b) {
if (startPos > numSize)
return -1;
if (b[startPos] > num) {
pos = startPos;
return 0;
}
int pos1, pos2;
int ans1 = find(num, startPos * 2, pos1, numSize, b),
ans2 = find(num, startPos * 2 + 1, pos2, numSize, b);
if (ans1 < 0 && ans2 < 0)
return -1;
else if (ans2 < 0) {
pos = pos1;
return 0;
}
else if (ans1 < 0) {
pos = pos2;
return 0;
}
else {
if (b[pos1] < b[pos2]) {
pos = pos1;
return 0;
}
else if (b[pos1] > b[pos2]) {
pos = pos2;
return 0;
}
else {
pos = mmin(pos1, pos2);
return 0;
}
}
}

int main() {
int M;
cin >> M;
myPriorityQueue<int> myQueue;

for (; M > 0; M--) {
char temp[100];
scanf("%s", temp);
if (strcmp(temp, "insert") == 0) {
int tempNum;
scanf("%d", &tempNum);
myQueue.push(tempNum);
}
else if (strcmp(temp, "find") == 0) {
int tempNum, pos;
scanf("%d", &tempNum);
find(tempNum, 1, pos, myQueue.size(), myQueue.queueData);
printf("%d\n", pos);
}
else {
int tempNum,v;
scanf("%d %d", &tempNum,&v);
myQueue.queueData[tempNum] -= v;

//向上过滤
for (auto i = tempNum; i > 1; i = i / 2) {
//判断是否比父结点更小
if (myQueue.queueData[i]<myQueue.queueData[i / 2]) {
//交换
auto temp = myQueue.queueData[i];
myQueue.queueData[i] = myQueue.queueData[i / 2];
myQueue.queueData[i / 2] = temp;
}
else break;
}

}
}

return 0;
}
``````

## Neight99's solution

``````#include <cstring>
#include <iostream>

using namespace std;

template <class Type>
class priorityQueue {
private:
int currentSize;
Type *array;
int maxSize;

void doubleSpace();
// void buildHeap();
void percolateDown(int);

public:
priorityQueue(int capacity = 20010);
// priorityQueue(const Type data[],int size);
~priorityQueue();
bool isEmpty() const;
void enQueue(const Type &x);
int find(Type, int, int &) const;
void decrease(const int &, const Type &);
Type deQueue();
};

template <class Type>
priorityQueue<Type>::priorityQueue(int capacity)
: maxSize(capacity), currentSize(0) {
array = new Type[capacity];
}

template <class Type>
priorityQueue<Type>::~priorityQueue() {
delete[] array;
}

template <class Type>
bool priorityQueue<Type>::isEmpty() const {
return currentSize == 0;
}

template <class Type>
return array[1];
}

template <class Type>
void priorityQueue<Type>::enQueue(const Type &x) {
if (currentSize == maxSize - 1) {
doubleSpace();
}

int hole = ++currentSize;
for (; hole > 1 && x < array[hole / 2]; hole /= 2) {
array[hole] = array[hole / 2];
}

array[hole] = x;
}

template <class Type>
Type priorityQueue<Type>::deQueue() {
Type minItem;

minItem = array[1];
array[1] = array[currentSize--];
percolateDown(1);

return minItem;
}

template <class Type>
void priorityQueue<Type>::percolateDown(int hole) {
int child;
Type tmp = array[hole];

for (; hole * 2 <= currentSize; hole = child) {
child = hole * 2;

if (child != currentSize && array[child + 1] < array[child]) {
child++;
}

if (array[child] < tmp) {
array[hole] = array[child];
} else {
break;
}
}
array[hole] = tmp;
}

template <class Type>
void priorityQueue<Type>::doubleSpace() {
Type *tmp = array;

maxSize *= 2;

array = new Type[maxSize];
for (int i = 0; i < currentSize; i++) {
array[i] = tmp[i];
}

delete[] tmp;
}

template <class Type>
int priorityQueue<Type>::find(Type x, int hole, int &pos) const {
int left, right, num1, num2;
if (hole > currentSize) {
pos = -1;
return 2147483647;
} else if (array[hole] > x) {
pos = hole;
return array[hole];
} else {
num1 = find(x, 2 * hole, left);
num2 = find(x, 2 * hole + 1, right);

if (num1 < num2) {
pos = left;
return num1;
} else if (num1 > num2) {
pos = right;
return num2;
} else {
if (left > right) {
pos = right;
} else {
pos = left;
}
return num1;
}
}
}

template <class Type>
void priorityQueue<Type>::decrease(const int &x, const Type &n) {
if (x > currentSize) {
return;
} else {
array[x] -= n;

if (n > 0) {
int tmp = x;
for (; (tmp / 2) != 0 && array[tmp / 2] > array[tmp]; tmp /= 2) {
Type temp = array[tmp];
array[tmp] = array[tmp / 2];
array[tmp / 2] = temp;
}
} else {
percolateDown(x);
}
}
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int m, x, n, ans;
char order[10];
priorityQueue<int> tree;

cin >> m;

for (int i = 0; i < m; i++) {
cin >> order;

if (strcmp(order, "insert") == 0) {
cin >> n;
tree.enQueue(n);
} else if (strcmp(order, "find") == 0) {
cin >> n;
tree.find(n, 1, ans);
cout << ans << '\n';
} else if (strcmp(order, "decrease") == 0) {
cin >> x >> n;
tree.decrease(x, n);
}
}

return 0;
}
``````

## skyzh's solution

``````#include <iostream>
#include <string>
#include <stack>
#include <cstring>

using namespace std;

template<typename T>
struct Heap {
T *data;
int cap, len;

Heap(int cap = 1024) : cap(cap + 1), len(0) {
data = new T[cap];
}

Heap(const Heap& that) : cap(that.cap), len(that.len) {
data = new T[cap];
memcpy(data, that.data, sizeof(T) * cap);
}

~Heap() { delete[] data; }

void push(const T &x) {
data[++len] = x;
swim(len);
}

T pop() {
swap(data[1], data[len--]);
sink(1);
return data[len + 1];
}

void top() {
return data[1];
}

bool less(int a, int b) {
if (a > len || b > len) return false;
return data[a] < data[b];
}

void swim(int idx) {
int _idx;
while (idx > 1 && less(idx, _idx = idx / 2)) {
swap(data[idx], data[_idx]);
idx = _idx;
}
}

void sink(int idx) {
int _idx;
while ((_idx = 2 * idx) <= len) {
if (_idx < len && less(_idx + 1, _idx)) _idx++;
if (less(idx, _idx)) break;
swap(data[idx], data[_idx]);
idx = _idx;
}
}

bool empty() {
return len == 0;
}
};

int main() {
Heap<int> heap(65536);
int N, op1, op2;
cin >> N;
char cmd[200];
for (int i = 0; i < N; i++) {
cin >> cmd;
if (strcmp(cmd, "insert") == 0) {
cin >> op1;
heap.push(op1);
}
else if (strcmp(cmd, "find") == 0) {
cin >> op1;
int _idx = -1;
for (int i = 1; i <= heap.len; i++) {
if (heap.data[i] > op1) {
if (_idx == -1 || heap.data[i] < heap.data[_idx]) {
_idx = i;
}
}
}
cout << _idx << endl;
}
else if (strcmp(cmd, "decrease") == 0) {
cin >> op1 >> op2;
heap.data[op1] -= op2;
heap.swim(op1);
}
}
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
using namespace std;

class heap {
private:
int *data;
int maxSize;
int size;

void doubleSpace() {
int *tmp = data;
data = new int[maxSize * 2 + 1];
for (int i = 1; i <= size; ++i) data[i] = tmp[i];
delete[]tmp;
maxSize *= 2;
}

public:
heap(int capacity = 10) : maxSize(capacity), size(0), data(new int[capacity + 1]) {}
~heap() {
delete [] data;
}
void enQueue(int n) {
if (size == maxSize) doubleSpace();
int hole = ++size;
for (; hole > 1 && n < data[hole >> 1]; hole = hole >> 1) data[hole] = data[hole >> 1];
data[hole] = n;
}
int find(int t, int n) {
if (t > size) return 0;
if (data[t] > n) return t;
int l = find(t << 1, n), r = find((t << 1) + 1, n);
if (l&&r) {
if (data[l] == data[r]) return (l < r ?  l : r);
else return (data[l] < data[r] ? l : r);
}
else if (l) return l;
else if (r) return r;
else return 0;
}
void decrease(int i, int d) {
int tmp = data[i] - d;
for (; i > 1 && tmp < data[i >> 1]; i = i >> 1) data[i] = data[i >> 1];
data[i] = tmp;
}
};

int main() {
ios::sync_with_stdio(false);
heap h;
int M; cin >> M;
char op[10];
int n, m;
for (int i = 0; i < M; ++i) {
cin >> op;
switch (op[0]) {
case 'i':
cin >> n;
h.enQueue(n);
break;
case 'f':
cin >> n;
cout << h.find(1, n) << endl;
break;
case 'd':
cin >> n >> m;
h.decrease(n, m);
}
}
return 0;
}
``````

## Zsi-r's solution

``````#include <cstring>
#include <iostream>

using namespace std;

class prioQueue
{
public:
int *array;
int currentSize;
int maxSize;
prioQueue(int capacity = 2) : currentSize(0), maxSize(capacity) { array = new int[maxSize]; }
~prioQueue() { delete[] array; }
void insert(int x);
int find(int x);
void decrease(int index, int sub);
void doublespace();
void percolateDown(int hole);
};

void prioQueue::doublespace()
{
int *tmp = array;
maxSize = maxSize * 2;
array = new int[maxSize];
for (int i = 0; i <= currentSize; i++)
array[i] = tmp[i];
delete[] tmp;
}

void prioQueue::insert(int x)
{
if (currentSize == maxSize - 1)
doublespace();
int hole = ++currentSize;
for (; hole > 1 && x< array[hole / 2]; hole /= 2)
array[hole] = array[hole / 2];
array[hole] = x;
}

/*
int prioQueue::find(int x) //找出优先级值大于x的最小的元素，输出其下标
{
if (array[1] == x)
{
if (currentSize == 2)
return 2;
else
return ((array[2] <= array[3]) ? 2 : 3);
}
for (int i = 1; i <= currentSize; i++)
if (array[i] == x)
{
break;
}
{
if (array[i] > x && array[i] < tmp)
{
tmp = array[i];
}
}
}
*/

int prioQueue::find (int x)
{
int tmp  = 1,i =1;
for (;tmp<currentSize;tmp++)
{
if (array[tmp]>x) break;
}
for (i = tmp ;i<= currentSize;i++)
{
if (array[i]>x && array[i]<array[tmp])
tmp = i;
}
return tmp;
}

void prioQueue::decrease(int index, int sub)
{
array[index] -= sub;
int tmp = array[index];
//percolateDown(1);
for (; index > 1 && tmp < array[index / 2]; index /= 2)
{
array[index] = array[index / 2];
}
array[index] = tmp;
}

void prioQueue::percolateDown(int hole)
{
int child;
int tmp = array[hole];
for (; hole * 2 <= currentSize; hole = child)
{
child = hole * 2;
if (child != currentSize && array[child + 1] < array[child])
child++;
if (array[child] < tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}

int main()
{
int line;
char operation[10];
int index, num;
cin >> line;
int *output = new int[line];
int j = 0;
prioQueue que;
for (int i = 0; i < line; i++)
{
cin >> operation;
if (strcmp(operation, "insert") == 0)
{
cin >> num;
que.insert(num);
}
else if (strcmp(operation, "find") == 0)
{
cin >> num;
output[j] = que.find(num);
j++;
}
else if (strcmp(operation, "decrease") == 0)
{
cin >> index >> num;
que.decrease(index, num);
}
//cout << endl;
//cout << "que : ";
//for (int t = 1;t<=que.currentSize;t++)
//    cout << que.array[t]<<' ';
}

for (int k = 0; k < j; k++)
cout << output[k] << endl;

return 0;
}
``````