优先队列Priority_Queue
2013年09月15日
⁄ 综合
⁄ 共 3130字 ⁄ 字号
小 中 大
// Priority_Queue.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <assert.h>
#include <iostream>
#include <algorithm>
class Max_Heapify...{
private:
int m_size;
public:
int Parent(int i)...{ return i/2; }
int Left(int i) ...{ return 2*i; }
int Right(int i) ...{return 2*i+1;}
void Max_Adus_Heapify(int A[],int i)
...{
int l = Left(i);
int r = Right(i);
int largest = i;
if((l <= m_size) && (A[l] > A[i]))//
largest = l;
//从元素A[Left(i)],A[Right(i)],A[i]找出最大的元素。
if((r <= m_size) && (A[r] >A[largest]))
largest = r;
//并将下标存放在largest中。如果A[i]最大，则以i为根的子树而使i及其子树满足堆的性质。
if (largest != i)
...{
std::swap(A[i], A[largest] );//
Max_Adus_Heapify(A, largest); //
}
//下标为largest的节点在交换后的值是A[i]，以该节点为根的子树又有可能违反最大堆的性质。因而要递归调用。
}
void Build_Max_Heapify(int A[])
...{
for(int i = m_size/2; i >= 0; i--)
Max_Adus_Heapify(A, i);
}
//建堆：子数组A[n/2+1...n]中的元素都是叶子节点，因此每个都可以看作只含一个元素的堆.
//m_size/2与m_size一样都正确，也就是上面句子的解释。
public:
Max_Heapify():m_size(NULL)...{}
Max_Heapify(int A[],int size)
...{
m_size = size-1;
Build_Max_Heapify(A);
}
void Heap_Sort(int A[])
...{
Build_Max_Heapify(A);
for(int i = m_size; i >= 1; i--)
...{
std::swap(A[0], A[i]);
--m_size;
Max_Adus_Heapify(A, 0);
}
}
//Build_Max_Heapify(),将使A[0]达到最大值。这样一直循环交换存放在数组A[i]中，递归调用。
~Max_Heapify()...{}
};
class Priority_Queue : private Max_Heapify...{
private:
int heap_size;
public:
Priority_Queue(int A[], int _size):Max_Heapify(A, _size)...{ heap_size = _size-1; }
int Heap_Maximum(int A[])...{return A[0];}//返回具有最大关键字的元素
int Heap_Extract_Max(int A[])//去掉并返回最大关键字元素
...{
assert( heap_size >= 0);
int max = A[0];
A[0] = A[heap_size];
heap_size = heap_size - 1;
Max_Adus_Heapify(A, 0);
return max;
}
void Heap_Increase_Key(int A[], int i, int key) //关键字增加的下标，是由对应的i来标识
...{
assert(key > A[i]);
A[i] = key;
while ((i >= 0) && (A[Parent(i)] < A[i]))
...{ //在移动的过程中，次元素不断地与其父母相比，如果次元素的关键字较大，
std::swap(A[i], A[Parent(i)]);//则交换它们的关键字且继续移动。当元素的关键字小于其父母时，
i = Parent(i);//此时最大堆性质成立，因此程序终止。
}
}
void Max_Heap_Insert(int A[], int key)
...{
heap_size = heap_size + 1;
A[heap_size] = -2147483648;
Heap_Increase_Key(A, heap_size, key);
}
~Priority_Queue()...{}
};
int main(int argc, char* argv[])
...{
int A[11] = ...{ 30, 45, 22, 72, 9, 12, 26, 80, 22, 43,1};
int size = sizeof(A)/sizeof(A[0]);
Priority_Queue p(A, size);
std::cout<<p.Heap_Maximum(A)<<std::endl;
std::cout<< p.Heap_Extract_Max(A)<<std::endl;
std::cout<<p.Heap_Maximum(A)<<std::endl;
p.Heap_Increase_Key(A,5,85);
std::cout<<p.Heap_Maximum(A)<<std::endl;
p.Max_Heap_Insert(A, 9999);
std::cout<<p.Heap_Maximum(A)<<std::endl;
// std::copy(A, A+11, std::ostream_iterator<int>(std::cout, " "));
return 0;
}