API tools faq
paste
Advertisement
sleepy_coder

Binomial Heap C++(lgn)

sleepy_coder
Jan 19th, 2019
252
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 18.05 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <assert.h>
  3. using namespace std;
  4.  
  5. #define debug(x) cout<<"Area "<<x<<" maybe safe\n";
  6.  
  7. template< typename T1 = int, typename T2 = int >
  8. struct Data{
  9.     T1 first;
  10.     T2 second;
  11.  
  12.     Data(){}
  13.     Data(T1 first, T2 second) : first(first), second(second) {}
  14.  
  15.     friend ostream &operator<<(ostream &os, const Data &data) {
  16.         os << "(" << data.first << ", " << data.second<<")";
  17.         return os;
  18.     }
  19.  
  20.     bool operator==(const Data &rhs) const {
  21.         return first == rhs.first &&
  22.                second == rhs.second;
  23.     }
  24.  
  25.     bool operator!=(const Data &rhs) const {
  26.         return !(rhs == *this);
  27.     }
  28.  
  29.     bool operator <(const Data &rhs) const {
  30.         return first < rhs.first;
  31.     }
  32.  
  33.     bool operator <=(const Data &rhs) const {
  34.         return first <= rhs.first;
  35.     }
  36.  
  37.     bool operator >(const Data &rhs) const {
  38.         return first > rhs.second;
  39.     }
  40.  
  41.     bool operator >=(const Data &rhs) const {
  42.         return first >= rhs.first;
  43.     }
  44.  
  45. };
  46.  
  47. //____________________________
  48.  
  49. template < typename T >
  50. struct ListNode{
  51. private:
  52.     T ListData;
  53.     ListNode *leftNode, *rightNode;
  54. public:
  55.     explicit ListNode(T data) : ListData(data) {
  56.         leftNode = rightNode = nullptr;
  57.     }
  58.  
  59.     T getListData() const {
  60.         return ListData;
  61.     }
  62.  
  63.     void setListData(T data) {
  64.         ListNode::ListData = data;
  65.     }
  66.  
  67.     ListNode *getLeftNode() const {
  68.         return leftNode;
  69.     }
  70.  
  71.     void setLeftNode(ListNode *leftNode) {
  72.         ListNode::leftNode = leftNode;
  73.     }
  74.  
  75.     ListNode *getRightNode() const {
  76.         return rightNode;
  77.     }
  78.  
  79.     void setRightNode(ListNode *rightNode) {
  80.         ListNode::rightNode = rightNode;
  81.     }
  82.  
  83.     virtual ~ListNode() {
  84.         this->leftNode = this->rightNode = nullptr;
  85.     }
  86.  
  87. } ;
  88. template < typename T >
  89. struct LinkedList{
  90. private:
  91.     ListNode<T> *headNode, *tailNode;
  92.     unsigned int listSize;
  93. public:
  94.     LinkedList(){
  95.         headNode = tailNode = nullptr;
  96.         listSize = 0;
  97.     }
  98.  
  99.     ListNode<T> *getHeadNode() const {
  100.         return headNode;
  101.     }
  102.  
  103.     void setHeadNode(ListNode<T> *headNode) {
  104.         LinkedList::headNode = headNode;
  105.     }
  106.  
  107.     ListNode<T> *getTailNode() const {
  108.         return tailNode;
  109.     }
  110.  
  111.     void setTailNode(ListNode<T> *tailNode) {
  112.         LinkedList::tailNode = tailNode;
  113.     }
  114.  
  115.     unsigned int getListSize() const {
  116.         return listSize;
  117.     }
  118.  
  119.     void setListSize(unsigned int listSize) {
  120.         LinkedList::listSize = listSize;
  121.     }
  122.  
  123.     void pushFront(T newData){
  124.         ListNode<T> *newNode = new ListNode<T>(newData);
  125.         if(!headNode){
  126.             headNode = tailNode = newNode;
  127.         }
  128.         else{
  129.             newNode->setRightNode(this->headNode);
  130.             this->headNode->setLeftNode(newNode);
  131.             this->headNode = newNode;
  132.         }
  133.         this->listSize++;
  134.     }
  135.  
  136.     void pushBack(T newData){
  137.         ListNode<T> *newNode = new ListNode<T>(newData);
  138.         if(!tailNode){
  139.             headNode = tailNode = newNode;
  140.         }
  141.         else{
  142.             newNode->setLeftNode(this->tailNode);
  143.             this->tailNode->setRightNode(newNode);
  144.             this->tailNode = newNode;
  145.         }
  146.         this->listSize++;
  147.     }
  148.  
  149.     T frontVal(){
  150.         assert(this->listSize!=0);
  151.         return this->headNode->getListData();
  152.     }
  153.  
  154.     T backVal(){
  155.         assert(this->listSize!=0);
  156.         return this->tailNode->getListData();
  157.     }
  158.  
  159.     void popFront(){
  160.         if(listSize != 0){
  161.             if(headNode == tailNode){
  162.                 delete headNode;
  163.                 headNode = tailNode = nullptr;
  164.             }
  165.             else{
  166.                 ListNode<T> *temp = headNode->getRightNode();
  167.                 temp->setLeftNode(nullptr);
  168.                 delete headNode;
  169.                 headNode = temp;
  170.             }
  171.             listSize--;
  172.         }
  173.     }
  174.  
  175.     void popBack(){
  176.         if(listSize != 0){
  177.             if(headNode == tailNode){
  178.                 delete tailNode;
  179.                 headNode = tailNode = nullptr;
  180.             }
  181.             else{
  182.                 ListNode<T> *temp = tailNode->getLeftNode();
  183.                 temp->setRightNode(nullptr);
  184.                 delete tailNode;
  185.                 tailNode = temp;
  186.             }
  187.             listSize--;
  188.         }
  189.     }
  190.  
  191.     void eraseAt(ListNode<T> *listNode){
  192.         if(listNode == nullptr)return;
  193.  
  194.         if(listNode == headNode)popFront();
  195.         else if(listNode == tailNode)popBack();
  196.         else{
  197.             listNode->getLeftNode()->setRightNode(listNode->getRightNode());
  198.             listNode->getRightNode()->setLeftNode(listNode->getLeftNode());
  199.             delete listNode;
  200.             listSize--;
  201.         }
  202.     }
  203.  
  204.     bool isEmpty(){
  205.         return this->listSize == 0;
  206.     }
  207.  
  208.     T getValAt(ListNode<T> *listNode){
  209.         assert(listNode != nullptr);
  210.         return listNode->getData();
  211.     }
  212.  
  213.     void showList(){
  214.         cout<<"List size: "<<getListSize()<<endl;
  215.         ListNode<T> *temp = headNode;
  216.         while(temp){
  217.             cout<<temp->getListData()<<" ";
  218.             temp = temp->getRightNode();
  219.         }
  220.         cout<<endl;
  221.     }
  222.  
  223.     virtual ~LinkedList() {
  224.         /*ListNode<T> *temp;
  225.         while(headNode){
  226.             temp = headNode;
  227.             headNode = headNode->getRightNode();
  228.             delete temp;
  229.         }
  230.         temp = headNode = tailNode = nullptr;
  231.         listSize = 0;*/
  232.     }
  233.  
  234. };
  235. //__________________________
  236.  
  237. template < typename T >
  238. struct TreeNode{
  239.     T nodeValue;
  240.     int degree, level;
  241.     TreeNode *leftChild, *parent, *rightSibling;
  242.  
  243.     TreeNode(T nodeValue) : nodeValue(nodeValue) {
  244.         this->degree = 0, this->level = 0;
  245.         leftChild = rightSibling = parent = nullptr;
  246.     }
  247.     friend TreeNode<T>* mergeBinomialTrees(TreeNode<T> *big, TreeNode<T> *small) {
  248.         if(big->nodeValue < small->nodeValue){
  249.             small->parent = big;
  250.             small->rightSibling = big->leftChild;
  251.             big->leftChild = small;
  252.             big->degree++;
  253.             return big;
  254.         }
  255.         else{
  256.             big->parent = small;
  257.             big->rightSibling = small->leftChild;
  258.             small->leftChild = big;
  259.             small->degree++;
  260.             return small;
  261.         }
  262.     }
  263. };
  264.  
  265. template < typename  T >
  266. LinkedList< TreeNode<T>* > unionLists(LinkedList< TreeNode<T>* > list1, LinkedList< TreeNode<T>* > list2){
  267.  
  268.     LinkedList< TreeNode<T>* > newList;
  269.     ListNode< TreeNode<T>* > *iterator_1, *iterator_2;
  270.  
  271.     iterator_1 = list1.getHeadNode(), iterator_2 = list2.getHeadNode();
  272.  
  273.     while(iterator_1 || iterator_2){
  274.         if(iterator_1 && iterator_2){
  275.             if(iterator_1->getListData()->degree <= iterator_2->getListData()->degree){
  276.                 newList.pushBack(iterator_1->getListData());
  277.                 iterator_1 = iterator_1->getRightNode();
  278.             }
  279.             else{
  280.                 newList.pushBack(iterator_2->getListData());
  281.                 iterator_2 = iterator_2->getRightNode();
  282.             }
  283.         }
  284.         else if(iterator_1){
  285.             newList.pushBack(iterator_1->getListData());
  286.             iterator_1 = iterator_1->getRightNode();
  287.         }
  288.         else{
  289.             newList.pushBack(iterator_2->getListData());
  290.             iterator_2 = iterator_2->getRightNode();
  291.         }
  292.     }
  293.  
  294.     return newList;
  295.  
  296. }
  297.  
  298. template < typename T >
  299. class Binomial_Heap
  300. {
  301.     unsigned int nodeCounter, treeCounter;
  302.     LinkedList< TreeNode<T>* > innerList;
  303.  
  304.     unsigned int countOnes(unsigned int n) {
  305.         unsigned int res = 0;
  306.         while(n && ++res) n -= n&(-n);
  307.         return res;
  308.     }
  309.     void heapify(LinkedList< TreeNode<T>* > list){
  310.  
  311.         innerList = list;
  312.  
  313.         if(list.getListSize() <= 1){
  314.             return;
  315.         }
  316.  
  317.         ListNode< TreeNode<T>* > *iterator_1, *iterator_2, *iterator_3;
  318.         iterator_1 = iterator_2 = iterator_3 = list.getHeadNode();
  319.  
  320.         if(list.getListSize() == 2){
  321.             iterator_2 = iterator_2->getRightNode();
  322.             iterator_3 = nullptr;
  323.         }
  324.         else{
  325.             iterator_2 = iterator_2->getRightNode();
  326.             iterator_3 = iterator_2;
  327.             iterator_3 = iterator_3->getRightNode();
  328.         }
  329.  
  330.         while(iterator_1){
  331.             if(iterator_2 == nullptr){
  332.                 iterator_1 = iterator_1->getRightNode();
  333.             }
  334.             else if(iterator_1->getListData()->degree < iterator_2->getListData()->degree){
  335.                 iterator_1 = iterator_1->getRightNode();
  336.                 iterator_2 = iterator_2->getRightNode();
  337.                 if(iterator_3)
  338.                     iterator_3 = iterator_3->getRightNode();
  339.             }
  340.             else if(iterator_3 &&
  341.                     iterator_1->getListData()->degree == iterator_2->getListData()->degree &&
  342.                     iterator_2->getListData()->degree == iterator_3->getListData()->degree) {
  343.  
  344.                 iterator_1 = iterator_1->getRightNode();
  345.                 iterator_2 = iterator_2->getRightNode();
  346.                 iterator_3 = iterator_3->getRightNode();
  347.             }
  348.             else if(iterator_1->getListData()->degree == iterator_2->getListData()->degree){
  349.                 if(iterator_1->getListData()->nodeValue < iterator_2->getListData()->nodeValue){
  350.                     //swap linked list consecutive nodes
  351.                     TreeNode<T>* temp = iterator_1->getListData();
  352.                     iterator_1->setListData(iterator_2->getListData());
  353.                     iterator_2->setListData(temp);
  354.                 }
  355.                 iterator_1->setListData( mergeBinomialTrees(iterator_1->getListData(), iterator_2->getListData()) );
  356.  
  357.                 ListNode< TreeNode<T>* > *iter = iterator_2->getRightNode();
  358.                 list.eraseAt(iterator_2);
  359.                 iterator_2 = iter;
  360.  
  361.                 if(iterator_3 != nullptr){
  362.                     iterator_3 = iterator_3->getRightNode();
  363.                 }
  364.             }
  365.         }
  366.  
  367.     }
  368.     void insertATreeInHeap(TreeNode<T>* treeNode){
  369.         LinkedList< TreeNode<T>* > temp;
  370.         temp.pushBack(treeNode);
  371.         heapify(unionLists(this->innerList, temp));
  372.     }
  373.     TreeNode<T> *getMinNodePtr(){
  374.  
  375.         LinkedList < TreeNode<T>* > _heap = innerList;
  376.         ListNode< TreeNode<T>* > *iterator_1 = _heap.getHeadNode();
  377.         TreeNode<T>* temp = iterator_1->getListData();
  378.  
  379.         while(iterator_1){
  380.             if(iterator_1->getListData()->nodeValue < temp->nodeValue){
  381.                 temp = iterator_1->getListData();
  382.             }
  383.             iterator_1 = iterator_1->getRightNode();
  384.         }
  385.         return temp;
  386.     }
  387.     T getValueAt(TreeNode<T>* treeNode){
  388.         if(treeNode == nullptr){
  389.             cout<<"invalid node pointer"<<endl;
  390.             assert(false);
  391.         }
  392.         return treeNode->nodeValue;
  393.     }
  394.     TreeNode<T> *searchValueATree(TreeNode<T>* root, T value){
  395.         if(!root)return nullptr;
  396.         else if(root->nodeValue == value)return root;
  397.         else {
  398.             TreeNode<T>* temp1 = searchValueATree(root->leftChild, value);
  399.             TreeNode<T>* temp2 = searchValueATree(root->rightSibling, value);
  400.             if(temp1)return temp1;
  401.             else return temp2;
  402.         }
  403.     }
  404.     TreeNode<T> *getNodePtr(T value){
  405.         LinkedList < TreeNode<T>* > _heap = innerList;
  406.         ListNode< TreeNode<T>* > *iterator_1 = _heap.getHeadNode();
  407.         while(iterator_1){
  408.             TreeNode<T>* nodePointer = searchValueATree(iterator_1->getListData(), value);
  409.             if(nodePointer)return nodePointer;
  410.             iterator_1 = iterator_1->getRightNode();
  411.         }
  412.         return nullptr;
  413.     }
  414.     LinkedList < TreeNode<T>* > getHeapTreeExcludeMin(TreeNode<T>* treeNode){
  415.         LinkedList< TreeNode<T>* > _heap;
  416.         TreeNode<T> *lo, *temp = treeNode->leftChild;
  417.         while(temp){
  418.             lo = temp;
  419.             temp = temp->rightSibling;
  420.             lo->rightSibling = nullptr;
  421.             _heap.pushFront(lo);
  422.         }
  423.         return _heap;
  424.     }
  425.  
  426. public:
  427.     Binomial_Heap(){
  428.         this->nodeCounter = this->treeCounter = 0;
  429.     }
  430.  
  431. //            Binomial_Heap(Binomial_Heap heap1, Binomial_Heap heap2){
  432. //                this->nodeCounter = heap1.nodeCounter + heap2.nodeCounter;
  433. //                this->treeCounter = heap1.treeCounter + heap2.treeCounter;
  434. //                this->innerList = unionLists(heap1.innerList, heap2.innerList);
  435. //                heapify(this->innerList);
  436. //            }
  437.  
  438.     void unionHeap(Binomial_Heap heap){
  439.         this->nodeCounter = this->nodeCounter + heap.nodeCounter;
  440.         this->treeCounter = this->treeCounter + heap.treeCounter;
  441.         this->innerList = unionLists(this->innerList, heap.innerList);
  442.         heapify(this->innerList);
  443.     }
  444.  
  445.     unsigned int getNodeCounter() const {
  446.         return nodeCounter;
  447.     }
  448.  
  449.     unsigned int getTreeCounter() {
  450.         treeCounter = countOnes(getNodeCounter());
  451.         return treeCounter;
  452.     }
  453.  
  454.     void insert(T newData){
  455.         insertATreeInHeap(new TreeNode<T>(newData));
  456.         nodeCounter++;
  457.     }
  458.  
  459.     T extractMin(){
  460.         LinkedList < TreeNode<T>* > _heap = innerList;
  461.         LinkedList < TreeNode<T>* > newHeap, lo;
  462.         TreeNode<T>* temp = getMinNodePtr();
  463.         T mini = temp->nodeValue;
  464.         ListNode< TreeNode<T>* > *iterator_1 = _heap.getHeadNode();
  465.  
  466.         while(iterator_1){
  467.             if(iterator_1->getListData()->nodeValue != temp->nodeValue){
  468.                 newHeap.pushBack(iterator_1->getListData());
  469.             }
  470.             iterator_1 = iterator_1->getRightNode();
  471.         }
  472.  
  473.         lo = getHeapTreeExcludeMin(temp);
  474.         heapify(unionLists(newHeap, lo));
  475.  
  476.         nodeCounter--;
  477.         return mini;
  478.     }
  479.  
  480.     T findMin(){
  481.         return getValueAt(getMinNodePtr());
  482.     }
  483.  
  484.     void printTree(TreeNode<T>* temp){
  485.         LinkedList< TreeNode<T>* > queueList;
  486.         unsigned int levelNo = 0;
  487.         temp->level = levelNo;
  488.         queueList.pushBack(temp);
  489.  
  490.         while(!queueList.isEmpty()){
  491.             if(queueList.frontVal()->leftChild){
  492.                 TreeNode<T> *curr = queueList.frontVal()->leftChild;
  493.                 curr->level = queueList.frontVal()->level + 1;
  494.                 while(curr){
  495.                     queueList.pushBack(curr);
  496.                     if(curr->rightSibling){
  497.                         curr->rightSibling->level = curr->level;
  498.                     }
  499.                     curr = curr->rightSibling;
  500.                 }
  501.             }
  502.             if(queueList.frontVal()->level > levelNo){
  503.                 cout<<endl;
  504.                 levelNo++;
  505.                 cout<<levelNo<<" -> ";
  506.  
  507.             }else if(levelNo==0){
  508.                 cout<<levelNo<<" -> ";
  509.             }
  510.             cout<<queueList.frontVal()->nodeValue<<" ";
  511.             queueList.popFront();
  512.         }
  513.         cout<<endl;
  514.     }
  515.  
  516.     void printHeap(){
  517.         LinkedList < TreeNode<T>* > _heap = innerList;
  518.         cout<<"//__________Heap___________"<<endl;
  519.         ListNode< TreeNode<T>* > *iterator_1 = _heap.getHeadNode();
  520.         unsigned int tree_cnt = 1;
  521.         while(iterator_1){
  522.             cout<<"Tree: "<<tree_cnt++<<endl;
  523.             printTree(iterator_1->getListData());
  524.             iterator_1 = iterator_1->getRightNode();
  525.         }
  526.         cout<<"___________________________//"<<endl;
  527.     }
  528.  
  529.     bool existsValue(T val){
  530.         return getNodePtr(val) != nullptr;
  531.     }
  532.  
  533.     void decreaseKey(T oldVal, T newVal){
  534.         LinkedList < TreeNode<T>* > _heap = innerList;
  535.         if(newVal < oldVal && existsValue(_heap, oldVal)){
  536.             TreeNode<T>* treeNode = getNodePtr(_heap, oldVal);
  537.             TreeNode<T>* parent = treeNode->parent;
  538.             treeNode->nodeValue = newVal;
  539.             while(parent && treeNode->nodeValue < parent->nodeValue){
  540.                 swap(parent->nodeValue, treeNode->nodeValue);
  541.                 treeNode = parent;
  542.                 parent = treeNode->parent;
  543.             }
  544.         }
  545.         else if(newVal > oldVal){
  546.             cout<<"#decrease Key error"<<endl;
  547.         }
  548.         innerList = _heap;
  549.     }
  550.  
  551.     void deleteFromBHeap(T val){
  552.         LinkedList < TreeNode<T>* > _heap = innerList;
  553.         if(_heap.getHeadNode() != nullptr && existsValue(_heap, val)){
  554.             decreaseKey(_heap, val, INT_MIN);
  555.             extractMin();
  556.             //no need to decrease nodeCounter as done in extract min
  557.         }
  558.     }
  559.  
  560. };
  561. //__________________________
  562.  
  563.  
  564.  
  565. int main(){
  566.  
  567.  
  568.     Binomial_Heap<int> heap1, heap2;
  569.     heap1.insert(10);
  570.     heap1.insert(20);
  571.     heap1.insert(30);
  572.     heap1.insert(40);
  573.     heap1.insert(50);
  574.     heap1.insert(60);
  575.     heap1.printHeap();
  576.  
  577.  
  578.     cout<<heap1.findMin()<<endl;
  579.     cout<< heap1.extractMin() << endl;
  580.     heap1.printHeap();
  581.  
  582.     heap2.insert(506);
  583.     heap2.insert(404);
  584.     heap2.printHeap();
  585.  
  586.     heap1.insert(10);
  587.     heap1.printHeap();
  588.  
  589.     heap1.unionHeap(heap2);
  590.     //Binomial_Heap<int> heap(heap1, heap2);
  591.     heap1.printHeap();
  592.     heap1.insert(333);
  593.     cout<<heap1.findMin()<<endl;
  594.     heap1.printHeap();
  595.     cout<<heap1.findMin()<<endl;
  596.     heap1.insert(4);
  597.     heap1.insert(44);
  598.     heap1.printHeap();
  599.     cout<<heap1.extractMin()<<endl;
  600.     heap1.printHeap();
  601.     heap1.printHeap();
  602.  
  603.     heap2.insert(555);
  604.     heap2.printHeap();
  605.     cout<<heap2.findMin()<<endl;
  606.     cout<<heap1.getNodeCounter()<<endl;
  607.     cout<<heap1.getTreeCounter()<<endl;
  608.     cout<<heap2.getNodeCounter()<<endl<<heap2.getTreeCounter()<<endl;
  609.  
  610. //    int n;
  611. //    Binomial_Heap<string> hep;
  612. //    cin>>n;
  613. //    while(n--){
  614. //        string a;
  615. //        cin>>a;
  616. //        hep.insert(a);
  617. //        cout<<hep.findMin()<<endl;
  618. //        hep.printHeap();
  619. //    }
  620.  
  621.  
  622. //    Binomial_Heap< Data<string, int> > heap;
  623. //    heap.insert(Data<string, int>("sabit", 47));
  624. //    heap.insert(Data<string, int>("Romiz", 48));
  625. //    heap.insert(Data<string, int>("Rithm", 46));
  626. //
  627. //    heap.printHeap();
  628. //    cout<<heap.findMin()<<endl<<" "<<heap.getNodeCounter()<<endl;
  629.  
  630.  
  631.     return 0;
  632. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!