# 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 to A

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

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, 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;

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