Skip to content
The Chat Archive
vicuna-33b Arena Human Preference 55K

implement priority_queue using heap in c++

  1. User

    implement priority_queue using heap in c++

  2. Assistant

    Here's an implementation of a priority queue using a binary heap in C++:

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    struct HeapElement {
        int value;
        HeapElement* parent;
        HeapElement* left;
        HeapElement* right;
    
        HeapElement(int val) : value(val), parent(nullptr), left(nullptr), right(nullptr) {}
    };
    
    class PriorityQueue {
    public:
        PriorityQueue() {
            head = new HeapElement(0);
            head->parent = head;
            size = 0;
        }
    
        ~PriorityQueue() {
            delete head;
        }
    
        void push(int val) {
            HeapElement* new_elem = new HeapElement(val);
            new_elem->parent = head;
            new_elem->left = head->left;
            new_elem->right = head;
            head->left->parent = new_elem;
            head->left = new_elem;
            size++;
    
            int parent_val = new_elem->value;
            while (new_elem->parent != head) {
                if (new_elem->parent->right == new_elem) {
                    swap(new_elem->parent->value, new_elem->value);
                    swap(new_elem->parent->right, new_elem->left);
                    new_elem = new_elem->parent;
                } else {
                    swap(new_elem->value, new_elem->parent->value);
                    new_elem = new_elem->parent;
                }
            }
        }
    
        int pop() {
            if (size == 0) {
                return -1;
            }
            int val = head->value;
            head = head->left;
            size--;
    
            int parent_val = head->value;
            while (head->parent != head) {
                if (head->parent->right == head) {
                    swap(head->parent->value, head->value);
                    swap(head->parent->right, head->left);
                    head = head->parent;
    
  3. User

    and explain this code

  4. Assistant

    Sure, here's an explanation of the code:

    1. HeapElement structure: This structure represents a single element in the binary heap. It has four pointers: value to store the value of the element, parent to point to the parent element in the heap, left to point to the left child element, and right to point to the right child element.
    2. PriorityQueue class: This class implements a priority queue using a binary heap. The constructor creates a new priority queue and initializes the head pointer to a new HeapElement with a value of 0. The size variable keeps track of the number of elements in the queue.
    3. push method: The push method adds a new element to the priority queue. It creates a new HeapElement with the given val and makes it a child of the head element. Then, it performs a heapify operation to ensure that the new element is correct

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.