【数据结构】堆heap，Trie树，位图Bitmap

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】堆heap，Trie树，位图Bitmap，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

本节研究堆heap、Trie树、位图Bitmap的实现；


堆

说明几点

（1）堆分为大根堆和小根堆；大根堆的根为最大值，每一个节点的值都不小于其孩子的值；

（2）可以利用大根堆实现升序排序；主要是利用大根堆的头和需要排序的最后一个数字交换的思想；

（3）使用大根堆实现最大优先级队列，类似stl中queue的操作，只是对于元素在队列中的元素优先级是不一样的，在最大优先级中，队列头为值最大元素；可利用大根堆来维护一个最大优先级队列；向优先级队列中push元素，类似像堆的末尾添加一个元素，然后使用_makeHeapUp寻找该元素的存放位置，进而维护大根堆；当向优先级队列中pop元素，将首元素和最后一个元素对换，然后使用_makeHeapDown来从首元素向下维护大根堆，类似堆排序，最后再将尾部元素pop_back；

（4）stl中使用sort_heap对容器进行堆排序，注意该容器需保证已经符合堆的特性；

（5）stl中使用make_heap对对一个容器中的值进行建堆；pop_heap，push_heap分别对队进行出堆（出堆之后，出堆值保存在容器的尾部）和入堆（入堆之前，入堆值已经保存在容器的尾部）；


堆排序

  1. inline int left(int parent)
  2. {
  3.   return parent*2 + 1;
  4. }
  5.  
  6. inline int right(int parent)
  7. {
  8.   return parent*2 + 2;
  9. }
  10.  
  11. inline int parent(int child)
  12. {
  13.   return (child-1) / 2;
  14. }
  15.  
  16. void _makeHeapDown(vector<int>& array,int top,int end)
  17. {
  18.   while (left(top) < end)
  19.     {
  20.       int leftChild = left(top);
  21.       int rightChild = right(top);
  22.  
  23.       int min = top;
  24.       if (array[top] < array[leftChild])
  25.         min = leftChild;
  26.  
  27.       if (rightChild < end && array[min] < array[rightChild])
  28.         min = rightChild;
  29.  
  30.       if (top == min)
  31.         break;
  32.  
  33.       swap(array[min],array[top]);
  34.  
  35.       top = min;
  36.     }
  37. }
  38.  
  39. void heapSort(vector<int>& array)
  40. {
  41.   for (int i = array.size() / 2; i >= 0; --i)
  42.     _makeHeapDown(array,i,array.size());
  43.  
  44.   for (int i = array.size()-1; i >= 1; --i)
  45.     {
  46.       swap(array[i],array[0]);
  47.       _makeHeapDown(array,i);
  48.     }
  49. }

说明几点：

（1）在堆排序中，仅仅使用了向下维护堆特性，但是优先级队列中使用了向上和向下维护堆特性；


优先级队列

  1. inline int left(int parent)
  2. {
  3.   return parent*2 + 1;
  4. }
  5.  
  6. inline int right(int parent)
  7. {
  8.   return parent*2 + 2;
  9. }
  10.  
  11. inline int parent(int child)
  12. {
  13.   return (child-1) / 2;
  14. }
  15.  
  16. void _makeHeapDown(vector<int>& array,array[top]);
  17.  
  18.       top = min;
  19.     }
  20. }
  21.  
  22. void _makeHeapUp(vector<int>& array,int last)
  23. {
  24.   if (last < 0)
  25.     return;
  26.  
  27.   int value = array[last];
  28.   while (last > 0)
  29.     {
  30.       int parentIndex = parent(last);
  31.  
  32.       if (array[parentIndex] < value)
  33.         {
  34.           array[last] = array[parentIndex];
  35.           last = parentIndex;
  36.         }
  37.       else
  38.         {
  39.           break;
  40.         }
  41.     }
  42.  
  43.   array[last] = value;
  44. }
  45.  
  46. class PriorityQueue
  47. {
  48. public:
  49.   int size() const
  50.   {
  51.     return _seq.size();
  52.   }
  53.  
  54.   bool empty() const
  55.   {
  56.     return _seq.empty();
  57.   }
  58.  
  59.   void push(int x)
  60.   {
  61.     _seq.push_back(x);
  62.     _makeHeapUp(_seq,_seq.size()-1);
  63.   }
  64.  
  65.   int top()
  66.   {
  67.     if (_seq.empty())
  68.       return -1;
  69.  
  70.     return _seq[0];
  71.   }
  72.  
  73.   void pop()
  74.   {
  75.     if (_seq.empty())
  76.       return;
  77.  
  78.     swap(_seq[0],_seq[_seq.size()-1]);
  79.     _makeHeapDown(_seq,_seq.size()-1);
  80.  
  81.     _seq.pop_back();
  82.   }
  83.  
  84. private:
  85.   vector<int> _seq;
  86. };


Trie树

基本知识

（1）Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的；

（2）根节点不包含字符，除根节点外每一个节点都只包含一个字符，节点保存对应的字符值；

（3）从根节点到某一节点，路径上经过的字符（节点）连接起来，为该节点对应的字符串；

（4）每个节点的所有子节点包含的字符都不相同；

（5）由于某些单词是其他单词的前缀，因此每一个节点增加是否为单词的标识；

（6）Trie树，即字典树，是一种树形结构，最大限度地减少无谓的字符串比较；典型应用是用于统计和排序大量的字符串（但不仅限于字符串）；


基本实现

  1. struct TrieNode
  2. {
  3.   char value;
  4.   vector<TrieNode*> children;
  5.   bool word;
  6. };
  7.  
  8. class Trie
  9. {
  10. public:
  11.   Trie()
  12.   {
  13.     root = new TrieNode();
  14.     root->word = false;
  15.   }
  16.  
  17.   ~Trie()
  18.   {
  19.     _deleteTrieNode(root);
  20.   }
  21.  
  22.   void insert(string s)
  23.   {
  24.     TrieNode* node = root;
  25.     for (int i=0; i < s.size(); ++i)
  26.       {
  27.         if (!isalpha(s[i]))
  28.           return;
  29.  
  30.         vector<TrieNode*>& children = node->children;
  31.         if (children.empty())
  32.           children.assign(26,NULL);
  33.  
  34.         int index = tolower(s[i]) - 'a';
  35.         if (children[index])
  36.           {
  37.             node = children[index];
  38.  
  39.             if (i == s.size()-1)
  40.               node->word = true;
  41.           }
  42.         else
  43.           {
  44.             TrieNode* child = new TrieNode();
  45.             child->value = s[i];
  46.  
  47.             if (i < s.size()-1)
  48.               {
  49.                 child->word = false;
  50.               }
  51.             else
  52.               {
  53.                 child->word = true;
  54.               }
  55.  
  56.             children[index] = child;
  57.  
  58.             node = child;
  59.           }
  60.       }
  61.   }
  62.  
  63.   bool search(string key)
  64.   {
  65.     TrieNode* node = root;
  66.     int i = 0;
  67.     bool flag = false;
  68.     for (i=0; i < key.size(); ++i)
  69.       {
  70.         if (!isalpha(key[i]))
  71.           return false;
  72.  
  73.         vector<TrieNode*>& children = node->children;
  74.         if (children.empty())
  75.           return false;
  76.  
  77.         int index = tolower(key[i]) - 'a';
  78.  
  79.         TrieNode* child = children[index];
  80.         if (child)
  81.           {
  82.             node = child;
  83.             flag = child->word;
  84.           }
  85.         else
  86.           {
  87.             return false;
  88.           }
  89.       }
  90.  
  91.     return flag;
  92.   }
  93.  
  94.   bool startsWith(string prefix)
  95.   {
  96.     TrieNode* node = root;
  97.     for (int i=0; i < prefix.size(); ++i)
  98.       {
  99.         if (!isalpha(prefix[i]))
  100.           return false;
  101.  
  102.         vector<TrieNode*>& children = node->children;
  103.         if (children.empty())
  104.           return false;
  105.  
  106.         int index = tolower(prefix[i]) - 'a';
  107.         TrieNode* child = children[index];
  108.         if (child)
  109.           {
  110.             node = child;
  111.           }
  112.         else
  113.           {
  114.             return false;
  115.           }
  116.       }
  117.  
  118.     return true;
  119.   }
  120.  
  121. private:
  122.   void _deleteTrieNode(TrieNode* node)
  123.   {
  124.     for (int i=0; node && i < node->children.size(); ++i)
  125.       _deleteTrieNode(node->children[i]);
  126.  
  127.     if (node)
  128.       delete node;
  129.   }
  130.  
  131.   TrieNode* root;
  132. };

说明几点

（1）本程序的Trie树的建立，仅仅建立对应的小写字符的字典树，对于大写字符将转换为小写字符；遇到非单词字符将会提前返回；

（2）在TrieNode中word标识该节点是否为一个单词；

（3）在析构函数中，利用递归来释放每一个节点的内存；


基本应用

描述：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。

解决办法：

（1）由于单词长度不超过10，建立Trie树也是可以忍受的，空间的花费不会超过（单词数*单词长度）个TrieNode；还且可以在边查询时边建立Trie树；

（2）若单词第一次出现，查询时建立Trie树，在最后一个节点标识该单词第一次出现的位置，可以修改TrieNode的word标识类型为int（默认值为-1），存放第一次出现的位置；

（3）若单词不是第一次出现，那么在查询到该单词最后一个字符时，该字符的word标识不为-1，说明已经该单词已经出现，word的值为该单词第一次出现的位置；


位图Bitmap

基本知识

（1）在C++中，我们可以直接使用bitset来进行位图相关的操作；

（2）位图可以使用在海量数据相关处理中，比如一个文件中含有1000亿个32位整数，请找出文件中未出现的整数；此时我们就可以使用位图，所有的32位数有2^32，即4G个数，那么4G个数可以使用4Gbit，即512MB内存来存放，然后遍历文件中的每一个数，对位图中相应的位置进行置位，最后找出位图中未置位的数就可以了；


基本实现

  1. template <unsigned N>
  2. class Bitmap final
  3. {
  4. public:
  5.   explicit Bitmap(unsigned val = 0):
  6.     _size((N-1)/32 + 1),_bits(_size,0)
  7.   {
  8.     _init(val);
  9.   }
  10.   
  11.   bool any() const
  12.   {
  13.     for (int i = 0; i < _bits.size(); ++i)
  14.     {
  15.       if (_bits[i] > 0)
  16.         return true;
  17.     }
  18.     
  19.     return false;
  20.   }
  21.   
  22.   bool none() const
  23.   {
  24.     return !any();
  25.   }
  26.     
  27.   void reset()
  28.   {
  29.     for (int i = 0; i < _bits.size(); ++i)
  30.       _bits[i] = 0;
  31.   }
  32.   
  33.   bool test(int pos) const
  34.   {
  35.     if (pos < 0)
  36.       return false;
  37.     
  38.     int m = pos / 32;
  39.     int n = pos % 32;
  40.     
  41.     return (_bits[m] & (1 << n)) > 0; 
  42.   }
  43.   
  44.   void set(int pos,bool flag)
  45.   {
  46.     if (pos < 0)
  47.       return;
  48.     
  49.     int m = pos / 32;
  50.     int n = pos % 32;
  51.     
  52.     if (flag) {
  53.       _bits[m] |= 1 << n; 
  54.     } else {
  55.       _bits[m] &= ~(1 << n); 
  56.     }
  57.   }
  58.   
  59.   void reset(int pos)
  60.   {
  61.     if (pos < 0)
  62.       return;
  63.     
  64.     int m = pos / 32;
  65.     int n = pos % 32;
  66.     _bits[m] &= ~(1 << n); 
  67.   }
  68.   
  69.   size_t size() const
  70.   {
  71.       return N;
  72.   }
  73.   
  74.   void print() const
  75.   {
  76.     for(int i = _bits.size()-1; i >= 0; --i)
  77.     {
  78.       cout << hex << _bits[i] << " ";
  79.     }
  80.     
  81.     cout << endl;
  82.   }
  83. private:
  84.   void _init(unsigned val)
  85.   {
  86.     int i = 0;
  87.     while (val > 0)
  88.     {
  89.       if (val & 0x01)
  90.       {
  91.         int m = i / 32;
  92.         int n = i % 32;
  93.         _bits[m] |= 1 << n; 
  94.       }
  95.       
  96.       val >>= 1;
  97.       ++i;
  98.     }
  99.   }
  100.   
  101.   int _size;
  102.   vector<int> _bits;
  103. };
  104.  
  105. int main(void)
  106. {
  107.   Bitmap<132> bits;
  108.   bits.print();
  109.   
  110.   cout << bits.test(0) << endl;
  111.   cout << bits.test(15) << endl;
  112.   cout << bits.test(16) << endl;
  113.   
  114.   bits.set(117,true);
  115.   bits.print();
  116.   cout << bits.test(16) << endl;
  117.   cout << bits.test(117) << endl;
  118.   
  119.   bits.reset(1);
  120.   bits.print();
  121.   
  122.   cout << dec << bits.size() << endl;
  123.   
  124.   cout << dec << bits.any() << endl;
  125.  
  126.   return 0;
  127. }
说明几点：

（1）该位图仅仅实现相关的基本操作，底层使用vector<int>来进行实现；

猜你在找的数据结构相关文章

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test