Lengkap

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

[login to view URL]();

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

[login to view URL](1,10);

}

Kemahiran: Pengaturcaraan C++, Pengaturcaraan C, Java, Algoritma, Kejuruteraan Perisian

Lihat lagi: minimum number enter user dimensional array java application, program queue priority, huffman queue priority, content to write for website, content write for website chennai, find a blogger to write for you, hire indian people to write for you, hire proffesional write for linkedin profile, hire someone to write for me in new york ny, hire someone to write for you, how do i find hockey bloggers to write for my website, how to write for a health site, i need a uk journalist to write for me, i need bloggers to write for my site, i need private writer to write for me in hr area, i want a writer who can write for me, online writers write for you, script write for hire in melbourne australia, what i have to write for order a commercial agency, where can i find bloggers to write for me

Tentang Majikan:
( 1 ulasan ) GUILDERLAND, United States

ID Projek: #22332683

Dianugerahkan kepada:

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

I can help you ___________________________________________ ___________________________________________

$30 USD dalam sehari
(4 Ulasan)
3.3
jbbunmat

I have been creating website and android app for almost 6 years I can even call my self a professional it's fun building a website I can create a wordpress website also I can create a real website Relevant Skills and Lagi

$15 USD dalam 3 hari
(0 Ulasan)
0.0