Write a C++ function to implement the insert operation in a max heap. bool Array

Question

Write a C++ function to implement the insert operation in a max heap.

bool ArrayMaxHeap::add(int newData)

void ArrayMaxHeap::siftUp(int subTreeRootIndex)

class ArrayMaxHeap {

private:

static const int ROOT_INDEX = 0; // Helps with readability

static const int DEFAULT_CAPACITY = 21; // Small capacity to test for a full heap

int* items; // Array of heap items

int itemCount; // Current count of heap items

int maxItems; // Maximum capacity of the heap

//Returns the array index of the left child (if it exists). int getLeftChildIndex(const int nodeIndex) const;

// Returns the array index of the right child (if it exists). int getRightChildIndex(int nodeIndex) const;

// Returns the array index of the parent node. int getParentIndex(int nodeIndex) const;

// Tests whether this node is a leaf. bool isLeaf(int nodeIndex) const;

// Creates a heap from an unordered array. void heapCreate();

public:

ArrayMaxHeap();

~ArrayMaxHeap();

// HeapInterface Public Methods:

bool isEmpty() const;

int getNumberOfNodes() const;

int getHeight() const;

int peekTop() const;

bool add(int newData);

bool remove(); void clear();

void siftDown(int subTreeRootIndex);

void siftUp(int subTreeRootIndex);

};

Explanation / Answer

int getParentIndex(int nodeIndex) {

            return (nodeIndex - 1) / 2;

}

    ArrayMaxHeap() {
       itemCount = ROOT_INDEX;
       maxItems =DEFAULT_CAPACITY;
       items= new (nothrow) int[maxItems];
    }

    void siftUp(int subTreeRootIndex) {

          int parentIndex, tmp;

          if (subTreeRootIndex != 0) {

                parentIndex = getParentIndex(subTreeRootIndex);

                if (items[parentIndex] > items[subTreeRootIndex]) {

                      tmp = items[parentIndex];

                      items[parentIndex] = items[subTreeRootIndex];

                      items[subTreeRootIndex] = tmp;

                      siftUp(parentIndex);

                }

          }

    }

    bool add(int newData) {

          if (itemCount == maxItems)

                return false;

          else {

                itemCount++;

                items[itemCount-1] = newData;

                siftUp(itemCount - 1);

                return true;

          }

    }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.