TA貢獻(xiàn)1848條經(jīng)驗 獲得超6個贊
/**
根據(jù)你需要java的要求， 寫了一個實現(xiàn)。
這個是一個整數(shù)最小優(yōu)先的堆，只實現(xiàn)了加入功能。
應(yīng)該還有刪除，清空等功能，但并不是必須的。
你可以自己嘗試實現(xiàn)。
測試為生成一組隨機數(shù)，加入隊列，每次加入后都察看一下堆的最優(yōu)先元素是多少。
如果還有疑問 ,
至郵件:tazerkinq@163.com
*/
public class Heap {
int[] heap; //堆的儲存空間
int size; //當(dāng)前的元素的數(shù)量
Heap() {
size = 0; //初始化數(shù)量為0
heap = new int[1024]; //預(yù)留空間1024,為了操作方便,0位置被棄用
}
void add(int e){ //加入新的元素,也是維護堆的主要地方之一
int i = ++size; //數(shù)量增加一, 并用臨時變量記錄此位置
while(( 1<i ) && ( e<heap[i/2] )){ //判斷e是否小于父節(jié)點的元素, 如否,則停止
heap[i] = heap[i/2]; //如是, 則移動父節(jié)點元素當(dāng)i記錄位置
i/=2; //i繼續(xù)向上迭代,指向剛才父節(jié)點的位置
}
heap[i] = e; //該位置即為元素最終位置
}
int peek(){ //返回堆頭的元素
return heap[1]; //數(shù)組下標(biāo)1的元素即是
} //當(dāng)然如果當(dāng)前元素為空的話,返回的則是初始值
int size(){ //返回當(dāng)前元素數(shù)目
return size;
}
public static void main(String[] args) {
Heap h = new Heap();
for(int i=0;i<100;i++){
int k=(int)(10000*Math.random()); //隨機生成一個整數(shù)
h.add(k); //加入到堆中
System.out.printf(
"Currently adding number is %5d.\t"+
"Currently priority number is %5d.%n",k,h.peek()); //輸出生成的隨機數(shù),并且輸出該堆的優(yōu)先元素
}
}
}
TA貢獻(xiàn)1824條經(jīng)驗 獲得超5個贊
最小堆的優(yōu)先隊列實現(xiàn)。
在建立最小堆或最大堆時。最主要的就是理解。SiftDown和SiftUp算法的實現(xiàn)問題。其實我覺得自己在畫一棵樹。先比較左右再比較父點之間。是最大堆往上。最小堆往下。就很能理解了，
下面程序是最小堆。
#include <iostream>
using namespace std;
template<class Elem>
class MinHeap
{
private:
Elem* heapArray;
int CurrentSize;
int MaxSize;
public:
MinHeap(const int n);
virtual~ MinHeap()
{
delete []heapArray;
}
void BuildHeap();
bool isLeaf(int pos) const;
int leftChild(int pos) const;
int rightChild(int pos) const;
//return parent position
int parent(int pos) const;
//刪除給定下標(biāo)的元素。
bool Remove(int pos,Elem& node);
void SiftDown(int left);
void SiftUp(int position);
bool Insert(const Elem& newNode);
Elem& RemoveMin();
bool print() const;
};
template<class Elem>
MinHeap<Elem>::MinHeap(const int n)
{
if(n<=0)
return ;
CurrentSize=0;
MaxSize=n;
heapArray=new Elem[MaxSize];
BuildHeap();
}
template<class Elem>
void MinHeap<Elem>::BuildHeap()
{
for(int i=CurrentSize/2-1;i>=0;i--)
SiftDown(i);
}
template<class Elem>
bool MinHeap<Elem>::isLeaf(int pos) const
{
return (pos>=CurrentSize/2) && (pos<CurrentSize);
}
template<class Elem>
int MinHeap<Elem>::leftChild(int pos) const
{
return 2*pos+1;
}
template<class Elem>
int MinHeap<Elem>::rightChild(int pos) const
{
return 2*pos+2;
}
template<class Elem>
int MinHeap<Elem>::parent(int pos) const
{
return (pos-1)/2;
}
//向下篩選。
template<class Elem>
void MinHeap<Elem>::SiftDown(int left)
{
int i=left; 。 //標(biāo)記父結(jié)點
int j=2*i+1;
Elem temp=heapArray[i];
while(j<CurrentSize)
{
if((j<CurrentSize-1) && (heapArray[j]>heapArray[i]))
j++; //指向右子結(jié)點
if(temp>heapArray[j])
{
heapArray[i]=heapArray[j];
i=j;
j=2*j+1;
}
else
break;
}
heapArray[i]=temp;
}
//向上篩選
template<class Elem>
void MinHeap<Elem>::SiftUp(int position)
{
int temppos=position;
Elem temp=heapArray[temppos];
while((temppos>0) && (heapArray[parent(temppos)]>temp))
{
heapArray[temppos]=heapArray[parent(temppos)];
temppos=parent(temppos);
}
heapArray[temppos]=temp;
}
template<class Elem>
bool MinHeap<Elem>::Insert(const Elem& newNode)
{
if(CurrentSize==MaxSize)
return false;
heapArray[CurrentSize]=newNode;
SiftUp(CurrentSize);
CurrentSize++;
return true;
}
template<class Elem>
Elem& MinHeap<Elem>::RemoveMin()
{
if(CurrentSize==0)
{
cout<<"Can't Delete ";
}
else
{
Elem temp=heapArray[0];
heapArray[0]=heapArray[CurrentSize-1];
CurrentSize--;
if(CurrentSize>1)
SiftDown(0);
return temp;
}
}
template<class Elem>
bool MinHeap<Elem>::Remove(int pos,Elem& node)
{
if((pos<0) || (pos>CurrentSize))
return false;
Elem temp=heapArray[pos];
heapArray[pos]=heapArray[--CurrentSize];
SiftUp(pos);
SiftDown(pos);
node=temp;
return true;
}
template<class Elem>
bool MinHeap<Elem>::print() const
{
if(CurrentSize<0)
return false;
for(int i=0;i<CurrentSize;i++)
cout<<heapArray[i]<<" ";
return true;
}
int main()
{
MinHeap<char> A(20);
char item;
int pos;
cout<<"Enter 20 number:"<<endl;
for(int i=0;i<20;i++)
{
cout<<"the"<<i<<"NO: ";
cin>>item;
A.Insert(item);
}
cout<<"\nPrint all the number: ";
A.print();
A.RemoveMin();
cout<<"\nAfter delete the Min number:";
A.print();
cout<<"\nEnter the positon you want:";
cin>>pos;
A.Remove(pos,item);
cout<<"\nThe data is:"<<item<<endl;
return 0;
}
//程序示例：
/*
Enter 20 number:
the0NO: a
the1NO: q
the2NO: z
the3NO: w
the4NO: s
the5NO: x
the6NO: e
the7NO: d
the8NO: c
the9NO: r
the10NO: f
the11NO: v
the12NO: t
the13NO: g
the14NO: b
the15NO: y
the16NO: h
the17NO: n
the18NO: u
the19NO: j
Print all the number: a c b d f t e h n j r z v x g y w q u s
After delete the Min number:c f b d r t e h n j s z v x g y w q u
Enter the positon you want:13
The data is:x
*/
給定一個數(shù)組，當(dāng)中有正負(fù)數(shù)，求當(dāng)中的一段“子數(shù)組”（即任意長度，連續(xù)的數(shù)字），使得這個“子數(shù)組”的和是所有“子數(shù)組”和中最大的，
如給定的數(shù)組為12， -8， 5， 66， -21， 0 ，35， -44，7，則最大的和的子數(shù)組為{12， -8， 5， 66， -21， 0 ，35}，最大的和為89.
package arraytest;
public class GetMaxArray {
// 復(fù)雜度為o（n^2）
public void findMax(int s[]) {
int add[] = new int[100];
int k = s[0];
int b = 0;// 標(biāo)記開始位置
int p = 0;// 標(biāo)記結(jié)束位置
int i;
int j;
for (i = 0; i <= s.length; i++)// 整體循環(huán)
{
for (j = i; j < s.length; j++)// 子數(shù)組循環(huán)
{
add[i] += s[j];
if (add[i] > k) {
k = add[i];
b = i;// 獲得開始位置下標(biāo)
p = j;// 獲得結(jié)束位置下標(biāo)
}
}
}
System.out.print("max sub array:");
System.out.print("{");
for (i = b; i <= p; i++) {
System.out.print(s[i] + " ");
}
System.out.println("}");
System.out.println("sum:" + k);
}
// 復(fù)雜度為o（n）
public int findMax(int a[], int size) {
int i, max = 0, temp_sum = 0;
for (i = 0; i < size; i++) {
temp_sum += a[i];
if (temp_sum > max)
max = temp_sum;
else if (temp_sum < 0)
temp_sum = 0;
}
System.out.print("sum:" + max);
return max;
}
public static void main(String[] args) {
int s[] =
// { 101, -100, 100, 100, 999, -222 - 100, 100 };
{ 12, -8, 5, 66, -21, 0, 35, -44, 7 };
GetMaxArray test = new GetMaxArray();
test.findMax(s);
test.findMax(s, s.length);
}
}
舉報