Forgot Password ??

PHP , ASP , ASP.NET, VB.NET, C#, Java , jQuery , Android , iOS , Windows Phone

	Registered : 109,027

HOME > PHP > PHP Forum > ช่วยแปลการทำงานให้เข้าใจหน่อย มันมากจัง งง BinaryHeap.h #ifndef _BINARY_HEAP_H_

ช่วยแปลการทำงานให้เข้าใจหน่อย มันมากจัง งง BinaryHeap.h #ifndef _BINARY_HEAP_H_

เริ่มหัวข้อใหม่

Guest

BinaryHeap.h >>>

#ifndef _BINARY_HEAP_H_
#define _BINARY_HEAP_H_

#include "dsexceptions.h"
#include "vector.h"

// BinaryHeap class
//
// CONSTRUCTION: with a negative infinity sentinel and
// optional capacity (that defaults to 100)
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// deleteMin( minItem ) --> Remove (and optionally return) smallest item
// Comparable findMin( ) --> Return smallest item
// bool isEmpty( ) --> Return true if empty; else false
// bool isFull( ) --> Return true if full; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Throws Underflow and Overflow as warranted

template <class Comparable>
class BinaryHeap
{
public:
explicit BinaryHeap( int capacity = 100 );

bool isEmpty( ) const;
bool isFull( ) const;
const Comparable & findMin( ) const;

void insert( const Comparable & x );
void deleteMin( );
void deleteMin( Comparable & minItem );
void makeEmpty( );

private:
int currentSize; // Number of elements in heap
vector<Comparable> array; // The heap array

void buildHeap( );
void percolateDown( int hole );
};

#include "BinaryHeap.cpp"
#endif

BinaryHeap.cpp >>>

#include "BinaryHeap.h"

/**
* Construct the binary heap.
* capacity is the capacity of the binary heap.
*/
template <class Comparable>
BinaryHeap<Comparable>::BinaryHeap( int capacity )
: array( capacity + 1 ), currentSize( 0 )
{
}

/**
* Insert item x into the priority queue, maintaining heap order.
* Duplicates are allowed.
* Throw Overflow if container is full.
*/
template <class Comparable>
void BinaryHeap<Comparable>::insert( const Comparable & x )
{
if( isFull( ) )
throw Overflow( );

// Percolate up
int hole = ++currentSize;
for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = array[ hole / 2 ];
array[ hole ] = x;
}

/**
* Find the smallest item in the priority queue.
* Return the smallest item, or throw Underflow if empty.
*/
template <class Comparable>
const Comparable & BinaryHeap<Comparable>::findMin( ) const
{
if( isEmpty( ) )
throw Underflow( );
return array[ 1 ];
}

/**
* Remove the smallest item from the priority queue.
* Throw Underflow if empty.
*/
template <class Comparable>
void BinaryHeap<Comparable>::deleteMin( )
{
if( isEmpty( ) )
throw Underflow( );

array[ 1 ] = array[ currentSize-- ];
percolateDown( 1 );
}

/**
* Remove the smallest item from the priority queue
* and place it in minItem. Throw Underflow if empty.
*/
template <class Comparable>
void BinaryHeap<Comparable>::deleteMin( Comparable & minItem )
{
if( isEmpty( ) )
throw Underflow( );

minItem = array[ 1 ];
array[ 1 ] = array[ currentSize-- ];
percolateDown( 1 );
}

/**
* Establish heap order property from an arbitrary
* arrangement of items. Runs in linear time.
*/
template <class Comparable>
void BinaryHeap<Comparable>::buildHeap( )
{
for( int i = currentSize / 2; i > 0; i-- )
percolateDown( i );
}

/**
* Test if the priority queue is logically empty.
* Return true if empty, false otherwise.
*/
template <class Comparable>
bool BinaryHeap<Comparable>::isEmpty( ) const
{
return currentSize == 0;
}

/**
* Test if the priority queue is logically full.
* Return true if full, false otherwise.
*/
template <class Comparable>
bool BinaryHeap<Comparable>::isFull( ) const
{
return currentSize == array.size( ) - 1;
}

/**
* Make the priority queue logically empty.
*/
template <class Comparable>
void BinaryHeap<Comparable>::makeEmpty( )
{
currentSize = 0;
}

/**
* Internal method to percolate down in the heap.
* hole is the index at which the percolate begins.
*/
template <class Comparable>
void BinaryHeap<Comparable>::percolateDown( int hole )
{
/* 1*/ int child;
/* 2*/ Comparable tmp = array[ hole ];

/* 3*/ for( ; hole * 2 <= currentSize; hole = child )
{
/* 4*/ child = hole * 2;
/* 5*/ if( child != currentSize && array[ child + 1 ] < array[ child ] )
/* 6*/ child++;
/* 7*/ if( array[ child ] < tmp )
/* 8*/ array[ hole ] = array[ child ];
else
/* 9*/ break;
}
/*10*/ array[ hole ] = tmp;
}
guide java code>>>>>

// HeapSort with ButtomUpHeap construction O(n + n*log(n)) = O(n*log(n))
// =======================================
public static void heapSort(Comparable[] V)

{
int n = V.length - 1;
Comparable[] T = new Comparable[V.length + 1];
for (int i = 0; i < V.length; i++) T[i + 1] = V ;
n = T.length - 1;
for (int i = n / 2; i > 0; i--) DownHeapBubbling(T, i, n);
for (int i = n; i > 1; i--)

{
swap(T, 1, i);
DownHeapBubbling(T, 1, i - 1);
}
for (int i = 0; i < V.length; i++) V = T[i + 1];
return;
}

public static void DownHeapBubbling(Comparable[] V, int i, int n)

{
int left = 2 * i;
int right = 2 * i + 1;
int high;
if (left <= n && V[left].compareTo(V ) > 0) high = left;
else high = i;
if (right <= n && V[right].compareTo(V[high]) > 0) high = right;
if (high != i)

{
swap(V, i, high);
DownHeapBubbling(V, high, n);
}
return;
}

มันเยอธจังคับ ยังไม่เข้าใจหลักการทำงาน

Tag : - - - -

Date : 31 ม.ค. 2550 12:14:51

By : เด็กกระจอก

View : 1960

Reply : 2

No. 1

arsachi

โพสกระทู้ ( 1,008 )
บทความ ( 0 )

ไปเอามาจากไหนหล่ะครับเนี่ยะ
รู้สึกว่าจะเป็น การหา ค่าเฉลี่ย และ ก้ค่า น้อย มาก ออกมาเป็น เปอร์ เพื่อ ทำกราฟ ครับ
เอามาหมดแล้วเหรอ รี้สึกว่ายังไม่หมด น่ะครับ มันหายไปบางส่วน น่ะ
มีบางไฟล์ หายไปเปล่า

Date : 31 ม.ค. 2550 12:56:15

By : arsachi

No. 2

Guest

ไปหาหนังสือ อัลกอลิซึม มาอ่าน นะครับ
เรื่อง heap

Date : 1 ก.พ. 2550 07:23:10

By : golem

ค้นหาข้อมูล

แสดงความคิดเห็น

Re : ช่วยแปลการทำงานให้เข้าใจหน่อย มันมากจัง งง BinaryHeap.h #ifndef _BINARY_HEAP_H_

รายละเอียด

เพื่อความเรียบร้อยของข้อความ ควรจัดรูปแบบให้พอดีกับขนาดของหน้าจอ เพื่อง่ายต่อการอ่านและสบายตา และตรวจสอบภาษาไทยให้ถูกต้อง

อัพโหลดแทรกรูปภาพ

Notice

เพื่อความปลอดภัยของเว็บบอร์ด ไม่อนุญาติให้แทรก แท็ก [img]....[/img] โดยการอัพโหลดไฟล์รูปจากที่อื่น เช่นเว็บไซต์ ฟรีอัพโหลดต่าง ๆ
อัพโหลดแทรกรูปภาพ ให้ใช้บริการอัพโหลดไฟล์ของไทยครีเอท และตัดรูปภาพให้พอดีกับสกรีน เพื่อความโหลดเร็วและไฟล์ไม่ถูกลบทิ้ง

เพื่อความปลอดภัยและการตรวจสอบ กระทู้ที่แทรกไฟล์อัพโหลดไฟล์จากที่อื่น อาจจะถูกลบทิ้ง

โดย

อีเมล์

บวกค่าให้ถูก

<= ตัวเลขฮินดูอารบิก เช่น 123 (หรือล็อกอินเข้าระบบสมาชิกเพื่อไม่ต้องกรอก)

Exchange: นำเข้าสินค้าจากจีน, Taobao, เฟอร์นิเจอร์, ของพรีเมี่ยม, ร่ม, ปากกา, power bank, แฟลชไดร์ฟ, กระบอกน้ำ

Load balance : Server 02