[cpp] maxheap

Viewer

  1. class MaxHeap
  2. {
  3.     //array of nodes
  4.     
  5.     vector<User> vec;
  6.  
  7.     //may want to make seperate node ffor bst and max heap 
  8.     //extarct max
  9.  
  10.     // return parent of `A[i]`
  11.     // don't call this function if `i` is already a root node
  12.     User parent(int i) {
  13.         return (- 1) / 2;
  14.     }
  15.     // return left child of `A[i]`
  16.     int left(int i) {
  17.         return (2*+ 1);
  18.     }
  19.     // return right child of `A[i]`
  20.     int right(int i) {
  21.         return (2*+ 2);
  22.     }
  23.     //heapify function, trickle up, given the inedx into the vector of the User 
  24.     void heapify(int i)
  25.     {
  26.         //reorder heap given an index and update the bst as we do a swap
  27.         // check if the node at index `i` and its parent violate the heap property
  28.         if (&& (vec[parent(i)]).votes < (vec[i]).votes)
  29.         {
  30.             // swap the two if heap property is violated
  31.             swap(vec[i], vec[parent(i)]); // will this work 
  32.  
  33.             // call heapify-up on the parent
  34.             heapify(parent(i));
  35.         }
  36.     }
  37.  
  38.     //insert a Uster
  39.     void insert(User)
  40.     {
  41.         /* insert into vector, insert the key which is a user
  42.          object but they key is the votes of that user */
  43.  
  44.     }
  45.     int extract_max()
  46.     {
  47.         //back 
  48.         //pop_back
  49.         //heapify_down
  50.             vec[0] = vec.back();
  51.             vec.pop_back();
  52.  
  53.             // call heapify-down on the root node
  54.             heapify_down(0);
  55.     }
  56.     // we do need a remove 
  57. };

Editor

You can edit this paste and save as new:


File Description
  • maxheap
  • Paste Code
  • 30 Nov-2021
  • 1.49 Kb
You can Share it: