[数据结构与算法]Note

谁借莪１个温暖的怀抱￠ 2021-12-05 22:27 201阅读 0赞

括号匹配

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//裁剪字符串，掐头去尾只保留被括号包围的部分
    void trim(const char exp[], int& lo, int& hi) {
        while ((lo <= hi) && (exp[lo] != '(') && (exp[lo] != ')'))
            lo++;
        while ((lo <= hi) && (exp[hi] != '(') && (exp[hi] != ')'))
            hi--;
    }
    //分割字符串，分割成左右，即"("与")"括号相同的多个部分
    int divide(const char exp[], int lo, int hi) {
        int mi = lo; int crc = 1;
        while ((0 < crc) && (++mi < hi))
        {
            if (exp[mi] == ')') crc--;
            if (exp[mi] == '(') crc++;
        }
        return mi;
    }
    //综合上述两部分，递归求解
    bool paren(const char exp[], int lo, int hi) {
        trim(exp, lo, hi);
        if (lo > hi) return true;
        if (exp[lo] != '(') return false;
        if (exp[hi] != ')') return false;
        int mi = divide(exp, lo, hi);
        if (mi > hi) return false;
        return paren(exp, lo + 1, mi - 1) && paren(exp, mi + 1, hi);
    }

对字符串形式的数学表达式求值

下面这段程序用到了指针的引用，与指针的主要区别在于调用函数中形参列表对其声明的方式不同，指针的声明形如：int\* a     指针的引用声明形如：int\*& a    其详细解读可网上搜索。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#define N_OPTR 9
    typedef enum { ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE } Operator;
    const char pri[N_OPTR][N_OPTR] = {
        '>','>','<','<','<','<','<','>','>',
        '>','>','<','<','<','<','<','>','>',
        '>','>','>','>','<','<','<','>','>',
        '>','>','>','>','<','<','<','>','>',
        '>','>','>','>','>','<','<','>','>',
        '>','>','>','>','>','>',' ','>','>',
        '<','<','<','<','<','<','<','=',' ',
        ' ',' ',' ',' ',' ',' ',' ',' ',' ',
        '<','<','<','<','<','<','<',' ','='
    };
    void readNumber(char*& p, stack<float>& stk) {
        float stkr;
        stk.push((float)(*p - '0'));
        while (isdigit(*(++p))) {
            stkr=stk.top() * 10 + (*p - '0');
            stk.pop();
            stk.push(stkr);
        }
        if ('.' != *p) return;
        float fraction = 1;
        while (isdigit(*(++p))) {
            stkr = stk.top() + (fraction /= 10) * (*p - '0');
            stk.pop();
            stk.push(stkr);
        }
    }
    Operator optr2rank(char op) {
        switch (op)
        {
        case '+':
            return ADD;
        case '-':
            return SUB;
        case '*':
            return MUL;
        case '/':
            return DIV;
        case '^':
            return POW;
        case '!':
            return FAC;
        case '(':
            return L_P;
        case ')':
            return R_P;
        case '\0':
            return EOE;
        default:
            exit(-1);
        }
    }
    char orderBetween(char op1, char op2) {
        return pri[optr2rank(op1)][optr2rank(op2)];
    }
    void append(char*& rpn, float opnd) {
        int n = strlen(rpn);
        char buf[64];
        if (opnd != (float)(int)opnd) sprintf(buf, "%.3f \0", opnd);
        else sprintf(buf, "%d \0", (int)opnd);
        rpn = (char*)realloc(rpn, sizeof(char)*(n + strlen(buf) + 1));
        strcat(rpn, buf);
    }
    void append(char*& rpn, char optr) {
        int n = strlen(rpn);
        rpn = (char*)realloc(rpn, sizeof(char) * (n + 3));
        //sprintf_s(rpn, "%c", optr);
        //char buf[64];
        sprintf(rpn+n, "%c ", optr);
        //const char o = optr;
        //strcat_s(rpn, sizeof(buf), buf);
        rpn[n + 2] = '\0';
    }
    float calcu(char op, float pOpnd) {
         //单目运算
        float sum = 1;
        if (pOpnd == 0)
            return 1;
        
        else
        {
            while (pOpnd)
            {
                sum *= (pOpnd--);
            }
        }
        return sum;
    }
    float calcu(float pOpnd1, char op, float pOpnd2) {
         //单目运算
        switch (op)
        {
        case '+':
            return pOpnd1 + pOpnd2;
        case '-':
            return pOpnd1 - pOpnd2;
        case '*':
            return pOpnd1 * pOpnd2;
        case '/':
            return pOpnd1 / pOpnd2;
        case '^':
            return pow(pOpnd1, pOpnd2);
        default:
            break;
        }
    }
    
    float evaluate(char* S, char*& RPN) {
        stack<float> opnd;
        stack<char> optr;
        optr.push('\0');
        while (!optr.empty())
        {
            if (isdigit(*S)) {
                readNumber(S, opnd);
                append(RPN, opnd.top());
            }else
                switch (orderBetween(optr.top(),*S))
                {
                case '<':
                    optr.push(*S); S++;
                    break;
                case '=':
                    optr.pop(); S++;
                    break;
                case '>': {
                    char op = optr.top();
                    optr.pop();
                    append(RPN, op);
                    if ('!' == op) {
                        float pOpnd = opnd.top();
                        opnd.pop();
                        opnd.push(calcu(op, pOpnd));
                    }
                    else
                    {
                        float pOpnd2 = opnd.top();
                        opnd.pop();
                        float pOpnd1 = opnd.top();
                        opnd.pop();
                        opnd.push(calcu(pOpnd1, op, pOpnd2));
                    }
                    break;
                }
                default:
                    exit(-1);
                }
        }
        return opnd.top();
    }

二叉搜索树

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma once
    #ifndef BINSEARCHTREE_H_
    #define BINSEARCHTREE_H_
    #include <stdlib.h>
    #include <stdint.h>
    #include <iostream>
    #include <exception>
    namespace alg {
        template<typename keyT,typename valueT>
        class BST {
        private:
            struct treeNode//树节点
            {
                keyT key;
                valueT value;
                treeNode *parent;
                treeNode *left;
                treeNode *right;
            };
            class BSTException :public std::exception {
         //用于异常处理的类
            public:
                virtual const char* what()const throw() {
                    return "key does not exist";
                }
            }excp_key;
        private://原始树根
            treeNode *m_root;
        private:
            BST(const BST&);
            BST& operator=(const BST&);
        public:
            BST() :m_root(nullptr) {};//构造函数，构造空树
            ~BST() {
                destruct_(m_root);
            }
            treeNode* find(const keyT &key) {
         //二叉搜索原理，树本身有序，按此原则往左右遍历比较
                treeNode *n = m_root;
                while (n != nullptr&&key != n->key)
                {
                    if (key < n->key)
                        n = n->left;
                    else
                        n = n->right;
                }
                return n;
            }
            void insert(const keyT &key, const valueT  &value) {
         //插入新的节点
                treeNode *z = new treeNode;//为新节点申请内存
                z->key = key;
                z->value = value;
                z->left = z->right = z->parent = nullptr;//先不关联任何节点
                treeNode *n = m_root;
                treeNode *y = nullptr;
                while (n!=nullptr)//不断深入左右子树，寻找合适的插入位置
                {
                    y = n;
                    if (key < n->key)
                        n = n->left;
                    else
                        n = n->right;
                }
                z->parent = y;
                if (y == nullptr)//二叉搜索树本身为空树，则插入节点直接作为根节点
                    m_root = z;
                else if (key < y->key)
                    y->left = z;
                else
                    y->right = z;
            }
            bool deleteKey(const keyT &key) {
                treeNode *z = find(key);
                if (z == nullptr)
                    return false;
                if (z->left == nullptr)
                    tansplant(z, z->right);
                else if (z->right == nullptr)
                    transplant(z, z->left);
                else {
                    treeNode *y = minimum(z->right);//找出右子树中最小的节点
                    if (y->parent != z) {
         //若最小节点不是孩子节点则进行替换
                        transplant(y, y->right);
                        y->right = z->right;
                        y->right->parent = y;
                    }
                    //对删除节点进行替换，替换为删除节点右子树中最小叶节点
                    transplant(z, y);
                    y->left = z->left;
                    y->left->parent = y;
                }
                delete z;
                return true;
            }
            void print_tree(treeNode *n, int indent) {
         //采用递归方式打印二叉搜索树，indent用于区分不同层次。
                if (n == nullptr)
                    return;
                print_tree(n->right, indent + 1);
                for (int i = 0; i < indent; ++i) {
                    std::cout << "   ";
                }
                std::cout << "[" << n->key << "," << n->value << "]" << std::endl;
                print_tree(n->left, indent + 1);
            }
            void print_helpler() {
                print_tree(m_root, 0);
            }
        private:
            void destruct_(treeNode *n) {
         //销毁节点n,逐级深入并销毁
                if (n == nullptr) return;
                destruct_(n->left);
                destruct_(n->right);
                delete n;
            }
            void transplant(treeNode *u, treeNode *v) {
         //将节点u替换为v
                if (u->parent == nullptr)
                    m_root = v;
                else if (u == u->parent->left)
                    u->parent->left = v;
                else
                    u->parent->right = v;
                if (v != nullptr)
                    v->parent = u->parent;
            }
            treeNode *minimum(treeNode *x) {
         //找出节点x所在子树中的最小key值节点，即最左叶节点
                while (x->left != nullptr)
                {
                    x = x->left;
                }
                return x;
            }
        };
    }
    #endif // !BINSEARCHTREE_H_

LUR缓存淘汰策略类

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

/*LRU(Least Recent Use):内存管理机制，页面置换算法，将最近使用最少的item丢弃*/
    #pragma once
    #ifndef LRU_CACHE_H_
    #define LRU_CACHE_H_
    #include <iostream>
    #include <string>
    #include <stdint.h>
    #include <stdio.h>
    #include <string.h>
    #include <map>
    using namespace std;
    namespace alg {
        template <typename K,typename V>
        class LRUCache{
            struct _Node_//LRU每个存储节点的形式
            {
                K key;
                V value;
                _Node_ *next;
                _Node_ *pre;
            } CacheNode;
        public:
            LRUCache(int cache_size = 10) {
                cache_size_ = cache_size;
                p_cache_list_head = new CacheNode;
                p_cache_list_near = new CacheNode;
                p_cache_list_head->next = p_cache_list_near;
                p_cache_list_head->pre = nullptr;
                p_cache_list_near->pre = p_cache_list_head;
                p_cache_list_near->next = nullptr;
            }
            ~LRUCache() {
                CacheNode *p;
                p = p_cache_list_head0->next;
                while (p != nullptr)
                {
                    delete p->pre;
                    p = p->next;
                }
                delete p_cache_list_near;
                cache_hash.clear();
            }
            V getValue(K key) {
          //获取key键指向的值
                if (cache_hash.find(key) != cache_hash.end()) {
         //存在则获取并返回
                    CacheNode *p = cache_hash[key];
                    detachNode(p);
                    addFirstNode(p);
                    return cache_hash[key]->value;
                }
                else {
         //不存在则给出提示
                    cout << "[ERROR]No key with name ::" << key << endl;
                    return V();
                }
            }
            bool putValue(K key, V value) {
         //存入新的key-value对。
                if (cache_hash.find(key) != cache_hash.end()) {
         //若已经存在相同key则更新value即可
                    cache_hash[key]->value = value;
                    detachNode((CacheNode*)cache_hash[key]);
                    addFirstNode((CacheNode*)cache_hash[key]);
                    if (cache_hash.size() > cache_size_) {
         //越界的节点删除掉
                        cout << "[INFO]LRU Cache is full ... Delete Last One..." << endl;
                        delEndNode();
                    }
                }
                else {
         //不存在相同key值节点则创建新的节点并作为首节点插入
                    CacheNode *p = new CacheNode;
                    p->key = key;
                    p->value = value;
                    addFirstNode(p);
                    cache_hash[key] = p;//并插入hash缓存中
                    if (cache_hash.size() > cache_size_) {
                        cout << "[INFO]LRU Cache is full ... Delete Last One..." << endl;
                        delEndNode();
                    }
                }
                return true;
            }
            void display() {
         //遍历所有节点并显示
                CacheNode p = p_cache_list_head->next;
                while (p!=nullptr)
                {
                    cout << " KEY[" << p->key << "]<==>VALUE[" << p->value << "]" << endl;
                    p = p->next;
                }
                cout << endl;
            }
        private: 
            int cache_size_;//LRU缓存的大小
            CacheNode *p_cache_list_head;//LRU头标记
            CacheNode *p_cache_list_near;//LRU尾标记，本身不存储内容，只作为指针指向内部。
            map<K, CacheNode*> cache_hash;//使用map数据结构来存储对应值
            void detachNode(CacheNode *node) {
         //将目标节点从LRU中分离出来
                node->pre->next = node->next;
                node->next->pre = node->pre;
            }
            void addFirstNode(CacheNode *node) {
         //将目标节点作为首节点加入
                node->pre = p_cache_list_head;
                if (cache_hash.empty()) {
                    node->next = p_cache_list_near;
                    p_cache_list_near->pre = node;
                    p_cache_list_head->next = node;
                }
                else {
                    node->next = p_cache_list_head->next;
                    p_cache_list_head->next->pre = node;
                    p_cache_list_head->next = node;
                }
            }
            void delEndNode() {
         //删除末尾节点
                CacheNode *p = p_cache_list_near->pre;
                detachNode(p);
                cout << "[INFO]Delete key ::: " << p->key << endl;
                cache_hash.erase(p->key);
                delete p;
            }
        };
    }
    #endif // !LUR_CACHE_H_

FISHER YATES'S SHUFFLE数组洗牌算法

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma once
    #ifndef SHUFFLE_H_
    #define SHUFFLE_H_
    #include <iostream>
    #include <stdlib.h>
    #include <time.h>
    namespace alg {
        template <typename T>
        static void shuffle(T *list, int len) {
         //对数组list中前len个数进行洗牌
            srand(time(nullptr));//生成随机数种子
            int i = len, j;
            T temp;
            if (i == 0) return;
            while (--i)
            {
                j = rand() % (i + 1);//随机打乱的位置
                temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }
        }
    }
    #endif // !SHUFFLE_H_

bitmap位图数据结构-数据压缩，图像处理常用

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma once
    #ifndef BITMAP_H_
    #define BITMAP_H_
    #include <memory>
    class Bitmap {
    private:
        char *M;
        int N;
    protected:
        void init(int n) { M = new char[N = (n + 7) / 8]; memset(M, 0, N); }//确保申请到够用的字符空间，采用(n+7)/8的方式向前取整。
    public:
        Bitmap(int n = 8) { init(n); }
        Bitmap(char *file, int n = 8) {
            init(n);
            FILE *fp = fopen(file, "r");
            fread(M, sizeof(char), N, fp);
            fclose(fp);
        }
        ~Bitmap() { delete[] M; }
        void set(int k) { expand(k); M[k >> 3] |= (0x80 >> (k & 0x07)); }
        void clear(int k) { expand(k); M[k >> 3] &= ~(0x80 >> (k & 0x07)); }
        bool test(int k) { expand(k); return M[k >> 3] &(0x80 >> (k & 0x07)); }
        void dump(const char *file) {
            FILE *fp = fopen(file, "w");
            fwrite(M, sizeof(char), N, fp);
            fclose(fp);
        }
        char* bit2string(int n) {
            expand(n - 1);
            char *s = new char[n + 1];
            s[n] = '\0';
            for (int i = 0; i < n; ++i) {
                s[i] = test(i) ? '1' : '0';
            }
            return s;
        }
        void expand(int k) {
            if (k < 8 * N) return;
            int oldN = N;
            char *oldM = M;
            init(2 * k);
            memcpy_s(M, N, oldM, oldN);
            delete[] oldM;
        }
    };
    #endif // !BITMAP_H_

二维数组

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma once
    //Date:2019/7/8 Start 19:20  End 21:15
    #ifndef ARRAY2D_H_
    #define ARRAY2D_H_
    #include <stdint.h>
    #include <stdlib.h>
    namespace alg {
        template <typename T = char>
        class Array2D {
        private:
            uint32_t NR;    //row of 2d-array
            uint32_t NC;    //column of 2d-array
            T *m_data;
        public:
            //constructor
            Array2D(uint32_t nrow, uint32_t ncol) {
                NR = nrow;
                NC = ncol;
                m_data = new T[nrow*ncol];
            }
            //destructor
            ~Array2D() {
                delete[] m_data;
            }
        private://声明为private，防止采用下面两种方式声明函数
            Array2D(const Array2D&);
            Array2D& operator=(const Array2D&);
        public:
            inline uint32_t row()const {
                return NR;
            }
            inline uint32_t col()const {
                return NC;
            }
            inline T& operator()(int row, int col) {
                return m_data[row*NC + col];
            }
            inline const T& operator()(int row, int col) const{
                return this->m_data[row*NC + col];
            }
            inline T* operator[](int row) { return &(m_data[row*NC]); }
            inline const T* operator[](int row) const { return &(m_data[row*NC]); }
            //set value by the giving number
            void clear(const T& value) {
                for (uint32_t i = 0; i < NC*NR; ++i) {
                    m_data[i] = value;
                }
            }
        };
    }
    
    #endif // !2DARRAY_H_

先进先出队列Queue

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

/*固定大小队列，先进先出
    function：dequeue队首出队；enqueue新元素入队，接到队尾；count返回队列元素个数，capacity返回队列总容量；
    is_empty判断队列是否空。front返回队首元素，队列空时该函数抛出异常。
    采用int数据类型记录容量，元素个数；指针存放元素；
    */
    #pragma once
    #ifndef MYQUEUE_H_
    #define MYQUEUE_H_
    #include <stdbool.h>
    #include <stdint.h>
    #include <exception>
    namespace alg {
        template <typename T>
        class Queue {
        private:
            class QueueEmptyException :public std::exception {
         //队列为空时，抛出异常。
            public:
                virtual const char *what() const throw() {
                    return "Queue is empty.";
                }
            }excp_empty;
        private:
            uint32_t m_capacity;    //capacity of queue;
            uint32_t m_size;        //当前队列大小
            uint32_t m_front;        //队首索引
            uint32_t m_rear;        //队尾索引
            T *m_elements;            //元素空间
        public:
            Queue(uint32_t max) {
          //构造函数
                this->m_elements = new T[max];
                this->m_capacity = max;
                this->m_size = 0;
                this->m_front = 0;
                this->m_rear = -1;
            }
            ~Queue() {
         //析构函数
                delete[] m_elements;
            }
        private://禁止一下两种方式声明定义以及初始化
            Queue(const Queue &);
            Queue& operator=(const Queue &);
        public:
            inline void dequeue() {
         //出队
                if (m_size == 0) {
                    return;
                }
                else
                {
                    m_size--;
                    m_front++;
                    if (m_front == m_capacity)
                        m_front = 0;
                }
            }
            bool enqueue(const T &element) {
         //入队
                if (m_size == m_capacity)//队列满，入队失败
                    return false;
                else//未满，成功入队
                {
                    m_size++;
                    m_rear++;
                    if (m_rear == m_capacity) {
         //队尾到达申请空间末端，则从申请空间头部开始存，循环利用
                        m_rear = 0;
                    }
                    m_elements[m_rear] = element;
                    return true;
                }
            }
            inline const T& front()const {
         //返回队首元素
                if (m_size == 0)//空队列则抛异常
                    throw excp_empty;
                return m_elements[m_front];
            }
            inline bool is_empty() {
         //判断是否为空队列
                if (m_size == 0) return true;
                return false;
            }
            inline uint32_t count() { return m_size; }//队列元素数量
            inline uint32_t capacity() { return m_capacity; }//队列总容量
        };
    }
    
    #endif // !MYQUEUE_H_

先进后出栈结构Stack

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

/*只愿得一人心，白首不分离
    堆栈数据结构，先进后出
    功能：查看栈是否空，入栈，出栈，查看栈顶元素，按下标索引查看栈内值
    */
    #pragma once
    #ifndef MYSTACK_H_
    #define MYSTACK_H_
    #include <stdint.h>
    #include <stdbool.h>
    #include <exception>
    namespace alg {
        template<typename T=uintptr_t>
        class Stack {
        private:
            class StackEmptyException :public std::exception {
            public:
                virtual const char *what() const throw() {
         //重载what函数，throw()没有参数表明不抛出任何异常，属于辅助函数。
                    return "stack is empty";
                }
            }excp_empty;
            class StackIndexOutOfBoundException :public std::exception {
         // 同上
            public:
                virtual const char *what() const throw() {
                    return "index out of bound";
                }
            }excp_ioob;
            uint32_t m_capacity;//最大容量
            uint32_t m_size;//当前栈内元素个数
            T *m_elements;//指针指向存放元素位置
        public:
            Stack(uint32_t capacity) {
          //constructor
                this->m_capacity = capacity;
                this->m_size = 0;
                this->m_elements = new T[capacity];
            }
            ~Stack() {
         //destructor
                delete[] m_elements;
            }
        private://声明为私有，防止采用下面两种方式来初始化
            Stack(const Stack&);
            Stack& operator=(const Stack&);
        public:
            inline bool is_empty() const { return m_size == 0 ? true : false; }//内联，判断栈是否为空
            inline void pop() {
                if (m_size) {
                    m_size--;
                }
                return;
            }
            inline const T& top()const {
         //内联，查看栈顶元素
                if (m_size == 0)throw excp_empty;
                return m_elements[m_size - 1];
            }
            inline bool push(const T& value) {
         //推出栈顶元素
                if (m_size == m_capacity) return false;
                else
                {
                    m_elements[m_size++] = value;
                    return true;
                }
            }
            inline uint32_t count()const { return m_size; }//返回栈内元素个数
            inline const T& operator[](uint32_t idx) const {
         //按索引查看栈内元素
                if (idx >= m_capacity)throw excp_ioob;
                return m_elements[m_size - 1 - idx];
            }
        };
    }
    #endif // !MYSTACK_H_

基于完全二叉树的二叉堆，min heap模式

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

/*基于完全二叉树的二叉堆结构，min heap模式。*/
    #pragma once
    #ifndef MYHEAP_H_
    #define MYHEAP_H_
    #include <iostream>
    #include <stdlib.h>
    #include <stdint.h>
    //#include <stdbool.h>
    #include <limits>
    namespace alg {
        template<typename T>
        class Heap {
            struct Elem//堆内节点结构
            {
                int key;
                T data;
            };
        private:
            int m_size;
            int m_max;
            Elem *m_heap;
        public:
            Heap(int msx) {
                this->m_max = max;
                this->m_size = 0;
                this->m_heap = new Elem[m_max];
            }
            ~Heap() {
                delete[] m_heap;
            }
        private:
            Heap(const Heap &);
            Heap& operator=(const Heap &);
            void swap(T &a, T &b) {
                T temp;
                temp = a;
                a = b;
                b = temp;
            }
        public:
            inline int count() const {
         //返回堆内元素个数
                return m_size;
            }
            void push(int key, const T &data) {
         //插入新的节点并更新堆序
                if (m_size == m_max) return;
                m_heap[m_size].key = key;
                m_heap[m_size].data = data;
                up(m_size);
                m_size++;
            }
            inline bool is_empty() const {
         //查看堆是否为空
                return (m_size == 0) ? true : false;
            }
            inline void clear() { m_size = 0; }
            bool contains(const T &data) {
         //查看堆内是否包含值为data的元素
                for (int i = 0; i < m_size; ++i) {
                    if (m_heap[i] == data) return true;
                }
                return false;
            }
            Elem pop() {
          //将堆顶元素推出并更新堆序
                int n = m_size - 1;
                swap(m_heap[0], m_heap[n]);
                down(0, n);
                m_size--;
                return m_heap[m_size];
            }
            bool remove(const T &data) {
         //删除数据值为data的首个节点并更新堆序
                for (int i = 0; i < m_size; ++i) {
                    if (m_heap[i.data == data) {
                        int n = m_size - 1;
                        if (n!=i)
                        {
                            swap(m_heap[i], m_heap[n]);
                            down(i, m_size);
                            up(i);
                        }
                        m_size--;
                        return true;
                    }
                }
                return false;
            }
            void decrease_key(const T &data, int newkey) {
         //更新键值
                if (remove(data)) {
                    push(newkey, data);
                }
            }
            void up(int j) {
         //将不符合二叉堆结构的节点向上交换传递
                for (;;) {
                    int i = (j - 1) / 2;
                    if (i == j || !less(j, i)) {
                        break;
                    }
                    swap(m_heap[i], m_heap[j]);
                    j = i;
                }
            }
            void down(int i, int n) {
         //将不符合二叉堆结构的节点向下交换传递
                for (;;) {
                    int j1 = 2 * i + 1;
                    if (j1 <= n || j1 < 0) break;
                    int j = j1;
                    int j2 = j1 + 1;
                    if (j2 < n && !less(j1, j2)) j = j2;
                    if (!less{ j,i }) break;
                    swap(m_heap[i], m_heap[j]);
                    i = j;
                }
            }
            void print_heap() {
         //遍历堆内元素
                for (int i = 0; i < m_size; ++i)
                    cout << "key:" << m_heap[i].key << " " << "value:" << m_heap[i].data;
                cout << endl;
            }
            bool less(int i, int j)//比较两节点key值大小
                return m_heap[i].key < m_heap[j].key;
        };
    }
    #endif // !MYHEAP_H_

转载于:https://www.cnblogs.com/lightmonster/p/11033070.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211205/e3eef13808ad4632a8be1287bd0d2764.png