Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #define INFINITY 99999999
- using namespace std;
- void swap(int *a, int *b)
- {
- int temp = *a;
- *a = *b;
- *b = temp;
- }
- class MaxPq{
- int initSize;
- int MaxSize;
- int *arr;
- int length;
- public:
- MaxPq();
- void Insert(int x);
- int FindMax();
- int ExtractMax();
- void IncreaseKey(int i, int newKey);
- void DecreaseKey(int i, int newKey);
- void Print();
- int FindElement(int n);
- void Heapify(int i);
- int getRight(int i);
- int getLeft(int i);
- int getParent(int i);
- };
- int main()
- {
- int choice;
- MaxPq q;
- while(1){
- cout<<"1. Insert"<<endl;
- cout<<"2. Find Max"<<endl;
- cout<<"3. Extract Max"<<endl;
- cout<<"4. Increase Key"<<endl;
- cout<<"5. Decrease Key"<<endl;
- cout<<"6. Print"<<endl;
- cout<<"7. Quit"<<endl;
- cout<<"Enter Your Choice"<<endl;
- cin>>choice;
- if(choice==1){
- int n;
- cout<<"Enter the number"<<endl;
- cin>>n;
- q.Insert(n);
- }
- else if (choice==2){
- int max = q.FindMax();
- cout<<"Max Element is: "<<max<<endl;
- }
- else if(choice==3){
- int max = q.ExtractMax();
- cout<<"Max = "<<max<<endl;
- cout<<"Max Extracted"<<endl;
- }
- else if (choice == 4){
- int i , key;
- cout<<"Enter Position"<<endl;
- int n = q.FindElement(i);
- cout<<"Element in "<<i<<"th position is "<<n<<endl;
- cout<<"Enter new value : ";
- cin>>key;
- q.IncreaseKey(i, key);
- //q.Heapify(i);
- }
- else if (choice == 5){
- int i , key;
- cout<<"Enter Position"<<endl;
- int n = q.FindElement(i);
- cout<<"Element in "<<i<<"th position is "<<n<<endl;
- cout<<"Enter new value : ";
- cin>>key;
- q.DecreaseKey(i, key);
- //q.Heapify();
- }
- else if(choice == 6){
- cout<<"The Queue is"<<endl;
- q.Print();
- }
- else if(choice == 7){
- cout<<"Quiting program"<<endl;
- break;
- }
- }
- }
- MaxPq::MaxPq() {
- initSize = 10;
- MaxSize = initSize;
- arr = new int[MaxSize];
- length = 0;
- }
- void MaxPq::Insert(int x) {
- if (length >= MaxSize ){
- arr = (int*) realloc(arr, sizeof(int)*(MaxSize+10));
- MaxSize = MaxSize+10;
- length = length+1;
- arr[length] = -INFINITY;
- IncreaseKey(length, x);
- }
- else{
- length = length+1;
- arr[length] = -INFINITY;
- IncreaseKey(length, x);
- }
- }
- int MaxPq::ExtractMax() {
- int max = arr[1];
- arr[1] = arr[length];
- length--;
- Heapify(1);
- return max;
- }
- int MaxPq::FindMax() {
- return arr[1];
- }
- void MaxPq::IncreaseKey(int i, int newKey) {
- arr[i] = newKey;
- while (i>1 && arr[getParent(i)]<arr[i]){
- swap(arr[i],arr[getParent(i)]);
- i = getParent(i);
- }
- }
- void MaxPq::DecreaseKey(int i, int newKey) {
- arr[i] = newKey;
- Heapify(i);
- }
- void MaxPq::Print() {
- for (int i = 1; i <=length ; i++) {
- cout<<arr[i]<<" ";
- }
- cout<<endl;
- }
- int MaxPq::FindElement(int n) {
- for (int i = 1; i <=length ; ++i) {
- if (arr[i]==n)
- return i;
- }
- return -1;
- }
- void MaxPq::Heapify(int i) {
- int largest = i;
- int left = getLeft(i);
- int right = getRight(i);
- if (left <= length && left>0){
- if (arr[left]>arr[i]){
- largest = left;
- }
- }
- if (right<=length && right>0){
- if(arr[right]>arr[largest]){
- largest = right;
- }
- }
- if (largest != i){
- swap(&arr[i],&arr[largest]);
- Heapify(largest);
- }
- }
- int MaxPq::getParent(int i) {
- if(i> 1 && i<length)
- return i/2;
- return -1;
- }
- int MaxPq::getRight(int i) {
- if(((2*i)+1)<length && i>=1)
- return (2*i)+1;
- return -1;
- }
- int MaxPq::getLeft(int i) {
- if((2*i)<length && i>=1)
- return 2*i;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement