- PR -

Binary Heap

1
投稿者投稿内容
NO
会議室デビュー日: 2003/03/02
投稿数: 15
投稿日時: 2003-03-05 04:21
Mark A.WeissのBinaryHeapの応用なのですが、大きい順に並べていって、もし前者より後者の方がvalueが大きい場合、secondary　areaにそのvalueをキープして置きたいのですが、具体的にそのareaのつくり方、そして、secondary　areaからprimary　heapへの移動のしかたがよくわかりません。private components　にはComparable[] areaを共有するようになっています。
お犬様
ベテラン
会議室デビュー日: 2003/01/26
投稿数: 67
投稿日時: 2003-03-09 02:14
まず、Mark A. Weiss の BinaryHeap と言われても何のことかわかりません。
恐らくheapソートとか優先待ち行列と呼ばれるアルゴリズムの一種でしょうが、
BinaryHeap ですら正確な事はわからないのに secondary area とか primary heap
とか言われても誰も答えられないと思いますよ。
NO
会議室デビュー日: 2003/03/02
投稿数: 15
投稿日時: 2003-03-09 06:39
Mark A. Weiss の BinaryHeap とは、array[0]をインデックスとして空けておくことです。つまり、deleteMin（or　deleteMax）はarray[1]になります。新しく入ってきたComparable　ｘは　deleteMin(or　Max）とexternal　area（class　Distributor）の　distribute　methodで比較され、もし、ｘがdeleteMinより小さい場合に、heap　treeのleafのところの、secondary　areaにkeepされるというものです。class　Distributorは、ファイルを読み込み、HeapAreaへデータを渡し、ソートをしてまた、書き込む作業をします。その際、method　Distributeで、Polyphase　sort/merge　が使われます。つまり、ここで、Fibonacci　sequenceが必要なのですが、この辺りも理解不足で...
このクラスはsomething　like...
/**
* n is the number of files to generate, inStream and outStream[] are Distributor's
* instance variable, seedRec is a concrete dummy object of the record.
* bSize makes an educated choice based on mSize, the available memory size.
*/
public Distributor(String inFile, String filePref, int n, int mSize,Sortable seekRec) {
this.heap= new HeapArea(mSize);
try{
this.inStream = new BufferedReader(new FileReader(inFile));
for(int i=0;0<n;i++){
String filename=filePref+(i+1);
//Creates a new buffered output stream to write data to the specified underlying
//output stream with the specified buffer size
this.outStream[i]= new BufferedOutputStream(new FileOutputStream(filename),bSize);
}
inStream.close();
}catch(FileNotFoundException e){
}catch(IOException e){
}
this.seedRec= new Sortable[0];//dummy
this.fileNum=n;
}
....

void　distribute
//ここで、Fibonacci　sequenceが使われるはず
this.heap=new HeapArea(bSize);

Sortable nextItem;　　
Sortable outputItem = this.heap.findMax();
while(this.heap.getPHeapSize() > 0){
if(this.heap.findMax().compareTo(outputItem)>0){
outputItem = this.heap.deleteMax();
out.writeObject(outputItem);
if( this.inStream.ready()){//more data in the input stream
nextItem = in.read(this.inStream);
if(nextItem.compareTo()<0||nextItem.compareTo()==0){
this.heap.insert(nextItem);
}
else{
this.heap.toss(nextItem);
}

}
}
}
}
//read1rec,write1rec, and markSeparator use methods readObject, writeObject, and writeSeparator.
private void write1rec(){
try{
Record theRecord = new Record(bSize);
DataOutputStream dos = new DataOutputStream(this.outStream[bSize]);
while(bSize<0){
dos.writeInt(theRecord.getID());
dos.writeFloat(theRecord.getSalary());
dos.writeChars(theRecord.getName());

dos.close();
dos.flush();
}
}catch(IOException ex){}
}
//read1rec,write1rec, and markSeparator use methods readObject, writeObject, and writeSeparator.
これも必要なはず
private void read1rec(){...}
　private void markSeparator(){...}
private void read1rec(){...}

//private　component
private HeapArea heap;
private BufferedReader inStream;
private BufferedOutputStream[] outStream;
private Sortable[] seedRec;
private int bSize;


勿論、これらのクラスもあります。

public class Record implements Sortable{

private int id;
private String name;
final private int field1Size = 3;
private float salary;
private boolean field3;
//private char field4;
private int recSize;

public Record(int recSize) {
this.recSize = recSize;
}

public Record(int id, float salary, String name,boolean f3,int recSize) {
this.id = id;
salary = salary;
name = name;
field3 = f3;
//field4 = f4;
this.recSize = recSize;
}

....
}

public interface Sortable {

public int compareTo(Sortable obj);//return negative 0, or positive if this<,=orobj
public Sortable createObject();//the factory method
public boolean isSeparator(Sortable obj);//return true if obj is a separator record
public void readObject(Reader r)throws IOException;//to read from raw data file
public void readObject(InputStream is)throws IOException;//to read from runs
public void writeObject(OutputStream os)throws IOException;
public void writeSeparator(OutputStream os)throws IOException;
public String toString();//to a format for display
}

public class MyIn extends DataInputStream implements Enumeration {
...
}
public class MyOut extends DataOutputStream implements MergeableOutput {

...
}

HeapAreaはこんな感じです。

public class HeapArea {
/**
* param size is the capacity(number of records) of the heap area.
*/
public HeapArea(int size) {
this.hSize=0;
this.sSize=0;
inOrder = true;
getArray(size);
area[ 0 ] =null;
}

/**
* Insert into the primary heap, maintaining heap order.
* x the item to insert.
* exception:
* NotInOrder if the primary heap has not been established
*/
public void insert(Sortable x)throws NotInOrder{
if(!this.inOrder){
put(x);
return;
}
checkSize();
// Percolate up
int hole = ++this.hSize;
area[ 0 ] = x;
for( ; x.compareTo(area[ hole / 2 ] ) > 0; hole /= 2 )
area[ hole ] = area[ hole/2 ];
area[ hole ] = x;
System.out.print("insert items "+area[ hole ]+"\n");
}

/**
* Insert into the heap area, without maintaining heaporder.
* @param x the item to insert.
*/
public void put(Sortable x){
checkSize();
this.area[++this.hSize]=x;
if((x.compareTo(this.area[this.hSize/2])) > 0)
this.inOrder=false;

}
/**
* Insert into the secondary area(without maintaining heap order.
* x the item to insert
*/
public void toss(Sortable x){
checkSize();
this.area[++this.sSize]=x;
this.inOrder=false;
}
/**
* Find the greatest item in the heap.
* ensure:
* return the greatest item.
* exception:
* Underflow if the primary heap heap is logically empty, false otherwise.
*/
public Sortable findMax()throws Underflow, NotInOrder{
if(this.isEmpty())
throw new Underflow("Empty binary heap");
if(!this.inOrder)
fixHeap();
return this.area[1];
}
/**
* Remove the greatest item from the primary heap and adjust the heap
* @return the greatest item.
* @exception:
* Underflow if the primary heap is empty, or NotInOrder if the primary
* heap has not been fixed.
*/
public Sortable deleteMax() throws Underflow, NotInOrder{
Sortable maxItem = findMax();
area[1]=area[this.hSize--];
percolateDown(1);
return maxItem;
}
/**
* Re-establish the heap order for the data collection in the area in linear time.
*/
public void fixHeap(){
for( int i = this.hSize / 2; i > 0; i-- )
percolateDown( i );
inOrder = true;
}
/**
* Re-establish the heap order for the size n at the beginning of the array
* for the items in the last n cells in linear time.
*/
public void fixHeap(int n){
for(int i= n/2 ; i>0 ; i-- )
percolateDown(i);

inOrder=true;
}


/**
* ensure:
* return true if the primary heap is logically empty, false otherwise.
*/
public boolean isEmpty(){
return hSize==0;
}
/**
* Make the entire array including the heap logically empty.
*/
public void makeEmpty(){
hSize=sSize=0;
}
/**
* @reutrn the number of node in the primary heap.
* exception:
* NotInOrder id the primary heap not been established.
*/
public int getPHeapSize()throws NotInOrder{
return this.hSize;

}
/**
* @return the number of nodes in the secondary storage area.
*/
public int getSAreaSize(){
return this.sSize;
}
/**
* Internal method to percolate down in the heap.
* @param hole the index at which the percolate begins.
*/
private void percolateDown(int hole){
int child;
Sortable tmp = area[hole];
for( ; hole*2 <= hSize ; hole = child){
child = hole*2;
if(child != hSize && (area[child+1].compareTo(area[child])<0))
child++;
if(area[child].compareTo(tmp)<0)
area[hole]=area[child];
else
break;
}

this.area[hole]=tmp;
}


/**
* Private method to allocate the heap array.
* Includes an extra spot for the sentinel.
* @param newMaxSize the capacity of the heap.
*/
private void getArray( int newMaxSize ){
area = new Sortable[ newMaxSize + 1 ];
}

/**
* Private method that doubles the heap array if full.
*/
private void checkSize( )
{
if( this.hSize == area.length - 1 )
{
Sortable [ ] oldArray = area;
getArray( hSize * 2 );
for( int i = 0; i < oldArray.length; i++ )
area[ i ] = oldArray[ i ];
}
}
private int hSize;//Number of elements in heap
private int sSize;//Number of items the secondary area
private boolean inOrder;//True if heap order is guaranteed in the primary heap
private Sortable[] area;//The array holding heap and secondary area

私の質問は、distributerのimplementの仕方が理解できないということです。
曖昧でスミマセンでした。



kwatch
会議室デビュー日: 2003/01/04
投稿数: 3
投稿日時: 2003-03-09 08:34
あれ、そうだっけ？
たしか、BinaryHeapは、ひとつの親に対して2人の子供があるからBinaryなのでは？
子供が3人、4人いるようなHeapも考えられますし。

一般に、n=0,1,2,....Nにおいて、ひとつの親に子供がk人いる場合、
親がn番目とすると、子供はkn+1番目〜kn+k番目になります。
これが一般のHeap。

ところがk==2のときは、nを0から始めると子供は2n+1番目と2n+2番目になるけど
nを1から始めると子供は2n番目と2n+1番目になって、ちょっとだけ簡潔になる。
だからMark Allen Weissも、BinaryHeapではarray[0]は使わずarray[1]から
使うようにしてるんじゃないかなー。
本読んだわけじゃないけど。

Google検索結果:

Mark Allen Weiss Homepage:
http://www.cs.fiu.edu/~weiss/

BinaryHeap.java:
http://www.cs.fiu.edu/~weiss/dsaajava/code/DataStructures/BinaryHeap.java


> Mark A. Weiss の BinaryHeap とは、array[0]をインデックスとして
> 空けておくことです。

上のJavaプログラムでは、array[0]は特にインデックスとしては使われてない
ようですよ。


それはおいといて、あなたの質問を読んでみましたが、残念ながら
何をいいたいのかよくわかりません。
secondary area? external area? ditribute method?
おちからになれず、残念です。

＃学校の宿題っぽい話ですね。
NO
会議室デビュー日: 2003/03/02
投稿数: 15
投稿日時: 2003-03-09 13:20
Binary Heap については一応解決したのですが（primary　areaはhSize、secondary　areaにはsSizeとすればよいだけのこと）polyphase　sort/mergeで使う、Fibonacci　sequenceがよく分からないのです。（どのように、distrubute()で使うのか）
public class Fibonacci {

public Fibonacci(int k) {
this.order=k;
init();
}
public int[] next(){
この部分のimplementの仕方が分かりません
このmethodはtrigger the computation for the next level.

}
public void display(){
int num=this.order;
int[] a = new int[num+1];
a[0]=0;
a[1]=1;
a[2]=1;
for (int i = 3; i <= num; i++){
a[i] = a[i-1] + a[i-2]; // （i>2）
System.out.println(i+": "+a[i]);

void　distribute()｛
//ここで、Fibonacci　sequenceが使われるはず
this.heap=new HeapArea(bSize);

Sortable nextItem;　　
Sortable outputItem = this.heap.findMax();
while(this.heap.getPHeapSize() > 0){
if(this.heap.findMax().compareTo(outputItem)>0){
outputItem = this.heap.deleteMax();
out.writeObject(outputItem);
if( this.inStream.ready()){//more data in the input stream
nextItem = in.read(this.inStream);
if(nextItem.compareTo()<0||nextItem.compareTo()==0){
this.heap.insert(nextItem);
}
else{
this.heap.toss(nextItem);
}

}
}
どなたかK-way　Sort/Mergeについてご存知の方はいらっしゃいますか？
maru
ぬし
会議室デビュー日: 2003/01/27
投稿数: 412
投稿日時: 2003-03-09 15:33
こんにちは。

＞Binary Heap については一応解決したのですが（primary　areaはhSize、secondary
＞areaにはsSizeとすればよいだけのこと）polyphase　sort/mergeで使う、Fibonacci
＞sequenceがよく分からないのです
結局どっち？解決した？解決したけど理解できていない？別の質問？

ＮＯさんの別の質問でもそうですが、結局なにを質問しようとしているのかがわかりません。
javaのAPI？アルゴリズム？技術書にかかれていること？アルゴリズムをどのようにコード化
するか？
質問のために参考でソースを添付するものひとつの手ですが、かなりで大きく、簡潔でなく
それでいて即実行できない部分的な抜粋だったり、日本語と英語の混在したご自分で命名した
命令名（変数名）か説明か分からないコメントだったり。
ソース中に「この部分のimplementの仕方が分かりません 」とあるけど、質問しているのは
この個所のこと？（とは読めないけど・・・？？？）
ソースもいつも間にやらフィボナッチ数列のクラスにすり替わっているし・・・？？？

それ以前に結局、ほかの質問は解決されたのですか？質問の内容からして高い（？）専門
レベルのような感じですが、一方的な質問で放置するのではなく、ひとつづつ片付けられ
てはいかがですか？（あまりえらそうなことを言える立場ではありませんが・・・）
kwatch
会議室デビュー日: 2003/01/04
投稿数: 3
投稿日時: 2003-03-10 09:35
You are not a native Japanese speaker, aren't you?
It may be the reason why your question is difficult to grasp.
I guess you must be a student of UNO

マージソートを行うときは、はじめにrunを複数のテープに分けますが、
このときrunの数をフィボナッチ数列でとなりあう数にすると、効率が
よくなります。

例えばデータ数が125個、1つのrunに5個のデータを入れるとすると、
全体で 125/5 = 21個のrunができますよね。

コード:
125個のデータ: 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 95 02 ....
               |------------| |------------| |------------| |---- ...
                   run1           run2          run3


＃今回の場合は、それぞれのrunの中を整列させるためにHeapSortを使うわけですね。


これを、3本のtapeを使ってmerge sortするとき、1本はデータ格納用と
して使うので、初期状態では2本のtapeにdistributeしないといけません。
このとき、フィボナッチ数列でとなりあう数のrunに分けるのです。

コード:
  Fib = 0, 1, 1, 2, 3, 5, 8, 13, 21, 33, 54, .....
                          ^   ^
                     21個のrunを8個と13個に分ける


なぜフィボナッチ数列を使うと効果的なのかは…説明が難しいですね。
次の動作図で考えてみてください。

コード:
tape1   tape2   tape3
-------------------------
  13       8       0      <== 初期状態。21個のrunを13個と8個に分ける
   5       0       8      <== runをmergeしてtape3に格納する。これを8回繰り返す。
   0       5       3      <== runをmergeしてtape2に格納する。これを5回繰り返す。
   3       2       0      <== runをmergeしてtape1に格納する。これを3回繰り返す。
   1       0       2      <== runをmergeしてtape3に格納する。これを2回繰り返す。
   0       1       1      <== runをmergeしてtape2に格納する。これを1回繰り返す。
   1       0       0      <== 完成！tape1にsortされた結果が残る


しょぼい説明ですが、わかりますか？
Javaのインプリメントはご自身でお考えください。

＃もし留学している日本人大学生なら、日本語に不自由はしないはずなので
＃もちっとわかりやすい質問にしてくださいね。

1

スキルアップ／キャリアアップ（JOB@IT）