[cpp] maxheap
Viewer
*** This page was generated with the meta tag "noindex, nofollow". This happened because you selected this option before saving or the system detected it as spam. This means that this page will never get into the search engines and the search bot will not crawl it. There is nothing to worry about, you can still share it with anyone.
- class MaxHeap
- {
- //array of nodes
- vector<User> vec;
- //may want to make seperate node ffor bst and max heap
- //extarct max
- // return parent of `A[i]`
- // don't call this function if `i` is already a root node
- User parent(int i) {
- return (i - 1) / 2;
- }
- // return left child of `A[i]`
- int left(int i) {
- return (2*i + 1);
- }
- // return right child of `A[i]`
- int right(int i) {
- return (2*i + 2);
- }
- //heapify function, trickle up, given the inedx into the vector of the User
- void heapify(int i)
- {
- //reorder heap given an index and update the bst as we do a swap
- // check if the node at index `i` and its parent violate the heap property
- if (i && (vec[parent(i)]).votes < (vec[i]).votes)
- {
- // swap the two if heap property is violated
- swap(vec[i], vec[parent(i)]); // will this work
- // call heapify-up on the parent
- heapify(parent(i));
- }
- }
- //insert a Uster
- void insert(User)
- {
- /* insert into vector, insert the key which is a user
- object but they key is the votes of that user */
- }
- int extract_max()
- {
- //back
- //pop_back
- //heapify_down
- vec[0] = vec.back();
- vec.pop_back();
- // call heapify-down on the root node
- heapify_down(0);
- }
- // we do need a remove
- };
Editor
You can edit this paste and save as new: