::Heap::

อัญชลี อริยะวุฒิพันธ์
483 06187 21


public class HeapNode {
	
	int priority;
	Object value;

	public HeapNode(int pri, Object val) {
		priority = pri;
		value = val;
	}
}

public class Heap {
	private final int DEFAULT_INITIAL_CAPACITY = 11;
	HeapNode[] heap;
	int size;

	public Heap() {
		heap = new HeapNode[DEFAULT_INITIAL_CAPACITY];
		size = 0;
	}

	public int size() {
		return size;
	}
	
	private int compare(HeapNode a, HeapNode b) {
		return a.priority - b.priority;
	}
	
	public HeapNode getMax() {
		return size==0? null: heap[0];
	}
	
	public HeapNode removeMax() {
		if (size == 0)
			return null;
		HeapNode re = heap[0];
		swap(0, --size);
		fixDown(0);
		return re;
	}
	
	public HeapNode find(Object x) {
		for (int i = 0; i < size; ++i)
			if (((Comparable) heap[i].value).compareTo(x) == 0)
				return heap[i];
		return null;
	}
	
	public void add(Object x, int p) {
		//ถ้ายังไม่มี x อยู่ใน heap ให้เพิ่มโนดที่มี value เท่ากับ x และ priority เท่ากับ p
		HeapNode a = find(x);
		if (a==null) {
			add(new HeapNode(p, (Comparable) x));
		} 
		//แต่ถ้ามี x อยู่แล้วให้เปลี่ยนค่า priority ให้เท่ากับ p 
		//แล้วปรับโครงสร้างของ heap ให้ถูกต้อง
		else {
			a.priority = p;
			for (int i = size - 1; i >= 0; --i)
				fixDown(i);
		}
	}
	
	public void add(HeapNode node) {
		HeapNode a = find(node.value);
		//หาว่า value ของ node มีอยู่แล้วหรือไม่่
		//ถ้ามี ก็ไม่ต้อง add
		if (a!=null) return;
		
		if (size == heap.length) {
			HeapNode[] newHeap = new HeapNode[size * 2];
			System.arraycopy(heap, 0, newHeap, 0, size);
			heap = newHeap;
		}
		heap[size++] = node;
		if (size > 1)
			fixUp();
	}


	public void remove(Object x) {
		if (size != 0){
			HeapNode a = find(x);
			if (a!= null){
				//หา index ของ x แล้วสลับตำแหน่ง x กับตัวสุดท้าย
				int index = indexOf(a);
				swap(size - 1, index);
				heap[--size] = null;
				fixDown(index);
			}
		}
	}

	private void fixUp() {
		int child = size - 1;
		int parent = (child - 1) / 2;
		while (child > 0) {
			//If child's priority <= parent's priority, do notihng.
			if (compare(heap[child], heap[parent]) <= 0)
				break;
			//If child's priority > parent's priority, swap.
			swap(child, parent);
			child = parent;
			parent = (child - 1) / 2;
		}
	}

	private void fixDown(int index) {
		int parent = index;
		int child = parent * 2 + 1;
		while (child < size) {
			if (child < size - 1 && compare(heap[child], heap[child + 1]) <= 0)
				++child;
			if (compare(heap[parent], heap[child]) >= 0)
				break;
			swap(parent, child);
			parent = child;
			child = parent * 2 + 1;
		}
	}

	
	// index of node
	private int indexOf(HeapNode node) {
		for (int i = 0; i < size; ++i)
			if (heap[i].equals(node))
				return i;
		return -1;
	}
	
	private void swap(int a, int b) {
		HeapNode temp = heap[a];
		heap[a] = heap[b];
		heap[b] = temp;
	}

	public HeapNode[] getHeap() {
		HeapNode[] newNode = new HeapNode[size];
		System.arraycopy(heap, 0, newNode, 0, size);
		return newNode;
	}
}

Hosted by www.Geocities.ws