SHARE
TWEET

Untitled

a guest Dec 3rd, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //HEAP
  2. void swap(int& a, int& b) {
  3.     int temp = a;
  4.     a = b;
  5.     b = temp;
  6. }
  7.  
  8. class Heap {
  9. private:
  10.     vector<int> data;
  11.  
  12.     int getLeft(int pos) {
  13.         return (pos * 2) + 1;
  14.     }
  15.  
  16.     int getRight(int pos) {
  17.         return (pos * 2) + 2;
  18.     }
  19.  
  20.     int getParent(int pos) {
  21.         return (pos - 1) / 2;
  22.     }
  23.  
  24.     void siftUp(int pos) {
  25.         int parent = getParent(pos);
  26.         while (data[pos] > data[parent]) {
  27.             swap(data[pos], data[parent]);
  28.             if (parent <= 0) {
  29.                 return;
  30.             }
  31.             parent = getParent(parent);
  32.             pos = getParent(pos);
  33.         }
  34.     }
  35.  
  36.     void siftDown(int pos) {
  37.         bool hasRight = getRight(pos) < data.size();
  38.         bool hasLeft = getLeft(pos) < data.size();
  39.  
  40.         if (hasRight && (data[pos] < data[getLeft(pos)] || data[pos] < data[getRight(pos)])) {
  41.             int swapWith = -1;
  42.             if (data[getLeft(pos)] < data[getRight(pos)]) {
  43.                 swapWith = getRight(pos);
  44.             } else {
  45.                 swapWith = getLeft(pos);  
  46.             }
  47.            
  48.             swap(data[pos], data[swapWith]);
  49.             siftDown(swapWith);
  50.         }
  51.         else if (hasLeft && data[pos] < data[getLeft(pos)]) {
  52.             swap(data[pos], data[getLeft(pos)]);
  53.             siftDown(getLeft(pos));
  54.         }
  55.     }
  56.  
  57. public:
  58.     bool isEmpty() const {
  59.         return data.size() == 0;
  60.     }
  61.     void add(int number) {
  62.         data.push_back(number);
  63.         if (data.size() != 0) {
  64.             siftUp(data.size() - 1);
  65.         }
  66.     }
  67.  
  68.     int peekTop() {
  69.         return data[0];
  70.     }
  71.  
  72.     void popTop() {
  73.         if (isEmpty()) {
  74.             return;
  75.         }
  76.  
  77.         swap(data[0], data[data.size() - 1]);
  78.         data.pop_back();
  79.         siftDown(0);
  80.     }
  81. };
  82.  
  83. //Levelorder BFS
  84. void levelorder() const {
  85.         queue<Node*> que;
  86.         que.push(root);
  87.  
  88.         while(!que.empty()) {
  89.             Node* current = que.front();
  90.             que.pop();
  91.             if (current) {
  92.                 cout << current->data << " ";
  93.              
  94.                 if (current->left) {
  95.                     que.push(current->left);
  96.                 }
  97.                 if (current->right) {
  98.                     que.push(current->right);
  99.                 }
  100.             }
  101.         }
  102.     }
  103.  
  104.  
  105.  
  106. //Depth first search
  107.  void _inorder(Node* current) const {
  108.         if (current) {
  109.             _inorder(current->left);
  110.             cout << current->data << " ";
  111.             _inorder(current->right);
  112.         }
  113.     }
  114.  
  115.     void _preorder(Node* current) const {
  116.         if (current) {
  117.             cout << current->data << " ";
  118.             _preorder(current->left);
  119.             _preorder(current->right);
  120.         }
  121.     }
  122.  
  123.     void _postorder(Node* current) const {
  124.         if (current) {
  125.             _postorder(current->left);
  126.             _postorder(current->right);
  127.             cout << current->data << " ";
  128.         }
  129.     }
  130.  
  131.  
  132. //HEAPIFY
  133. void heapify(int arr[], int n, int i)
  134. {
  135.     int largest = i; // Initialize largest as root
  136.     int l = 2*i + 1; // left = 2*i + 1
  137.     int r = 2*i + 2; // right = 2*i + 2
  138.  
  139.     // If left child is larger than root
  140.     if (l < n && arr[l] > arr[largest])
  141.         largest = l;
  142.  
  143.     // If right child is larger than largest so far
  144.     if (r < n && arr[r] > arr[largest])
  145.         largest = r;
  146.  
  147.     // If largest is not root
  148.     if (largest != i)
  149.     {
  150.         swap(arr[i], arr[largest]);
  151.  
  152.         // Recursively heapify the affected sub-tree
  153.         heapify(arr, n, largest);
  154.     }
  155. }
  156.  
  157. // main function to do heap sort
  158. void heapSort(int arr[], int n)
  159. {
  160.     // Build heap (rearrange array)
  161.     for (int i = n / 2 - 1; i >= 0; i--)
  162.         heapify(arr, n, i);
  163.  
  164.     // One by one extract an element from heap
  165.     for (int i=n-1; i>=0; i--)
  166.     {
  167.         // Move current root to end
  168.         swap(arr[0], arr[i]);
  169.  
  170.         // call max heapify on the reduced heap
  171.         heapify(arr, i, 0);
  172.     }
  173. }
RAW Paste Data
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!
 
Top