// ConsoleApplication46.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#include<conio.h>
#include<string>
#define maxsize 10
using namespace std;
struct node
{
string data;
int prn;
};
class heap_priority
{
node a[maxsize];
int count;
public:
heap_priority()
{
count = 0;
}
bool insert(int key, string name)
{
if (count == maxsize)
return false;
else
a[count].data = name;
a[count].prn = key;
moveup(count++);
return true;
}
void moveup(int index)
{
int parent = (index - 1) / 2;
node bottom = a[index];
while (index > 0 && a[parent].prn < bottom.prn)
{
a[index] = a[parent];
index = parent;
parent = (parent - 1) / 2;
}
a[index] = bottom;
}
void *remove()
{
if (count == 0)
{
cout << "\n heap is empty" << endl;
return NULL;
}
node *root = new node;
root->data = a[0].data;
root->prn = a[0].prn;
a[0] = a[--count];
movedown(0);
return root;
}
void movedown(int index)
{
int larger_child;
node top = a[index];
while (index < count / 2)
{
int left_child = 2 * index + 1;
int right_child = 2 * index + 2;
if (right_child < count&&a[left_child].prn < a[right_child].prn)
larger_child = right_child;
else
larger_child = left_child;
if (top.prn >= a[larger_child].prn)
break;
a[index] = a[larger_child];
index = larger_child;
}
a[index] = top;
}
void display()
{
for (int i = 0; i < count; i++)
cout << "["<<i<<"] [" << a[i].data << "|" << a[i].prn << "]";;
cout << endl;
}
};
void main()
{
heap_priority h;
h.insert(2, "alpha");
h.insert(3, "beta");
h.insert(2, "gamma");
h.insert(4, "delta");
h.insert(1, "omega");
h.display();
h.insert(3, "lambda");
h.display();
h.remove();
h.display();
_getch();
}
0 التعليقات:
إرسال تعليق