Question
Transcribed Text
Programming Part: Min-Max Heap
A
min-max heap is a data structure that supports both deleteMin and deleteMax in O(log N) per
operation. The structure is identical to a binary heap, but the hemp-order property is that for any node, X,
at even depth, the element stored at x is smaller than the parent but larger than the grandparent (where
this makes sense), and for any node x at odd depth, the element stored at x is larger than the parent
but smaller than the grandparent (see figure 1).
6
(81)
(87
(14)
(17)
(12)
(28)
71
25)
80
20)
(52)
78
31
(42)
(31)
(59
16)
24
(79)
63
18)
19
32)
13)
15)
48)
Figure 1: A min-max heap.
Using an array to represent the min-max heap structure (in the same way as for min hemp or max
heap), implement the following operations.
1. buildHeap: Builds a min-max heap from a list of naturals read from standard input.
2. findMin and findMax: Returns the minimum (resp the maximum) element.
3. insertHeap: Inserts a new element into the min-max heap.
4. deleteMin and deleteNax: Deletes the minimum (resp the maximum) element.
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
#ifndef BINARYHEAP_H#define BINARYHEAP_H
#include<vector>
#include <iostream>
using namespace std;
template <typename Comparable>
class BinaryHeap
{
public:
explicit BinaryHeap( int capacity = 100);
bool isEmpty( ) const;
const Comparable & findMin( ) const;
const Comparable & findMax( ) const;
void insertHeap( const Comparable & x );
void deleteMin( );
void deleteMax( );
void buildHeap(const vector<Comparable> & input );
bool level(int hole);
private:
int currentSize; // Number of elements in heap
vector<Comparable> array; // The heap array
void minUp(int hole);// reset item of heap from the current hole upward in min order
void maxUp(int hole); // reset item of heap from the current hole upward in max order
void minDown(int hole);// reset item of heap from the current hole downward in min order
void maxDown(int hole);// reset item of heap from the current hole downward in max order
void swap(Comparable & c1, Comparable & c2);// swap value of 2 variable
};...
Return to homework library