# Heap Ordered Array

Write a function, ValidHeap(), to test is an array conforms heap ordered binary tree. This function returns true is the array is heap ordered, false if not.

Examples:

Given A= [33, 65, 55, 64, 37, 25, 33, 34, 87, 0, 48, 95],

ValidHeap(A,7) returns true since all parent nodes conform k >= 2k and k>=2k+1 rules for 7 items, that are from A[1] to A[8]

ValidHeap(A,9) returns false since k=4 fails k >= 2k test (A[4] < A[8])

Make sure that the ValidHeap function has these parameters: array and size of heap-ordered tree. As you notice, the array size is not a parameter.

Note that for binary heap trees, the first item, A[0], does not have any meaning for the tree structure, which may be ignored or used for some other purposes

In your program, ask the user to enter a number between 0 - 11, and show return value of ValidHeap() for A= [33, 65, 55, 64, 37, 25, 33, 34, 87, 0, 48, 95].

PS: For this assignment, You may just expand the below existing code with your new function since it has already sink / swim-up functions.

// Binary Heap Tree for Priority Queue

#include <iostream>

#include <stdio.h>

#include <string>

#include <stdlib.h>

#include <iomanip> // std::setw

// #define N 10

using namespace std;

class BinaryHeap

{

public:

BinaryHeap(); // Construction

bool less(int i, int j);

void exch(int i, int j);

void swim(int k);

void sink(int k);

bool isEmpty();

int size();

void insert(int v);

int delMax();

void ListArray();

void printT(int x, int id);

private:

int N = 0;

int *pq;

int capacity = 100;

};

// Initialize the class

BinaryHeap::BinaryHeap()

{

pq = new int[capacity];

cout << "A new priority queue with " << capacity << " capacity was created...!" << endl ;

}

void BinaryHeap::ListArray()

{

for (int i=1; i <= N; i++) // Remember we have "size" items

{

cout << pq[i] << ", ";

}

}

void BinaryHeap::swim(int k)

{

while (k > 1 && less(k/2, k))

{

exch(k/2, k);

k = k/2;

}

}

bool BinaryHeap::isEmpty()

{ return N == 0; }

int BinaryHeap::size()

{ return N; }

void BinaryHeap::insert(int v)

{

pq[++N] = v;

swim(N);

}

int BinaryHeap::delMax()

{

int max = pq[1];

exch(1, N--);

pq[N+1] = NULL;

sink(1);

return max;

}

void BinaryHeap::sink(int k)

{

while (2*k <= N)

{

int j = 2*k;

if (j < N && less(j, j+1)) j++;

if (!less(k, j)) break;

exch(k, j);

k = j;

}

}

bool BinaryHeap::less(int i, int j)

{

if (pq[i] < pq[j])

return true;

return false;

}

void BinaryHeap::exch(int i, int j)

{

int t = pq[i]; pq[i] = pq[j]; pq[j] = t;

}

//1-> 2, 3

//2-> 4, 5

//3-> 6, 7

void BinaryHeap::printT(int x, int id)

{

if (x>N) return;

printT(2*x+1,id+10);

cout << setw(id) << ' ' << pq[x] << endl;

printT(2*x,id+10);

}

// The program lunches here

int main( )

{

BinaryHeap BH;

for (int i=0; i < 20; i++)

[login to view URL]( rand()%50 +1);

cout<< " ------\n ";

}

Tentang Majikan:
( 1 ulasan ) GUILDERLAND, United States

ID Projek: #22332683

VnNorthStar

Hi I'm ready for the project. I'm an expert in Java & algorithms I read your specifications and I'm sure I can do it perfectly.

\$20 USD dalam 2 hari
(44 Ulasan)
4.3

## 4 pekerja bebas membida secara purata \$24 untuk pekerjaan ini

profvipabutaleb

I'm computer engineering TA with 10+ years of experience. Experienced with the data structures and advanced data structures types Experienced with BGI / DOS Programming / 80x96 program development and games developmen Lagi

\$30 USD dalam sehari
(100 Ulasan)
5.6
MaLiguo