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。

Input Format

第一行含有一个正整数M（1<=M<=20000),代表总的操作数。

以下M行，每行一个操作。

Output Format

对于每个find操作，输出一个下标。回车分隔。

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();
    Type getHead() const;
};

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>
Type priorityQueue<Type>::getHead() const {
    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);
    }
    int xaddress = 1;
    for (int i = 1; i <= currentSize; i++)
        if (array[i] == x)
        {
            xaddress = i;
            break;
        }
    int maxaddress = ((xaddress * 2 <= currentSize) ? (xaddress * 2) : currentSize);
    int tmp = array[maxaddress];
    int tmpaddress = maxaddress;
    for (int i = xaddress / 2; i <= maxaddress; i++)
    {
        if (array[i] > x && array[i] < tmp)
        {
            tmp = array[i];
            tmpaddress = i;
        }
    }
    return tmpaddress;
}
*/

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;
}