heap.java

java算法大全

import java.awt.*;
import java.util.*;

class Heap extends Node {

    Font bigFont, smallFont, tinyFont, hugeFont, fixFont;
    DrawingPanel drawingPanel;
    Node tree, posn;
    Vector nodeList, posnList, inputList, outputList, heapArray;
    int max_node_per_level, depth;
    Node movingNode;
    boolean exchanging;
    Point[] aPoints;
    Color darkgreen = new Color(0, 140, 0);
    Color darkRed = new Color(140, 0, 0);
    Color darkBlue = new Color(0, 0, 140);
    ComBox runningCom;
    int max_size;

    public Heap(DrawingPanel drawingPanel, int max_size) {
	this.bigFont = drawingPanel.bigFont;
	this.smallFont = drawingPanel.smallFont;
	this.tinyFont = drawingPanel.tinyFont;
	this.hugeFont = drawingPanel.hugeFont;
	this.fixFont = drawingPanel.fixFont;
	this.drawingPanel = drawingPanel;
	this.max_size = max_size;
	this.tree = null;
	nodeList = new Vector();
	posnList = new Vector();
	inputList = new Vector();
	heapArray = new Vector();
	outputList = new Vector();
	calNodesCoord(max_size);
	hideMovingNode();
	exchanging = false;
	runningCom = null;
    }

    public void redraw() {
	drawingPanel.repaint();
	drawingPanel.delay();
    }

    public void initHeap() {
	this.tree = null;
	nodeList = new Vector();
	inputList = new Vector();
	heapArray = new Vector();
	outputList = new Vector();
	exchanging = false;
    }

    public void setInput(int[] a) {
	inputList = new Vector();
	for (int i = 0; i < a.length; i++) {
	    Node node = new Node(a[i]);
	    node.x = drawingPanel.offset + 30 + (i+1)*22;
	    node.y = bottomMostPosn(posn) + 85;
	    inputList.addElement(node);
	}
	redraw();
    }

    public void addInput(int i) {
	Node node = new Node(i);
	node.x = drawingPanel.panel_width - drawingPanel.offset - 50;
	node.y = bottomMostPosn(posn) + 50;
	inputList.addElement(node);
	runningCom = new ComBox(node.x - 120, node.y + 50,
		"input arriving...", Color.blue, Color.yellow, fixFont);
	redraw();
    }

    public void delFirstInput() {
	inputList.removeElementAt(0);
    }

    public void addOutput(int i) {
	Node node = new Node(i);
	node.y = drawingPanel.offset;
	node.x = drawingPanel.offset + 80 + (outputList.size())*22;

	runningCom = new ComBox(150, node.y + 20,
		"Extracting output...", Color.blue, Color.yellow, fixFont);

	movingNode = new Node(-1);
	int srcX = movingNode.x = drawingPanel.offset + 20;
	int srcY = movingNode.y = ((Node)posnList.firstElement()).y;
	if (!heapArray.isEmpty()) {
	    Node heapNode;
	    if (!nodeList.isEmpty())
		heapNode = (Node)nodeList.firstElement();
	    else {
		heapNode = (Node)posnList.firstElement();
		movingNode.setWeight(i);
		movingNode.x = heapNode.x;
		movingNode.y = heapNode.y;
	    }

	    Node arrayNode = (Node)heapArray.firstElement();

	    if (!nodeList.isEmpty()) {
	    	heapNode.setRightNode(null); 
		heapNode.setLeftNode(null);
	    }
	    int srcHx = heapNode.x;
	    int srcAy = arrayNode.y;
	    for (int k = 0; k < 5; k++) {
		if (!nodeList.isEmpty())
		    heapNode.x += (srcX - srcHx)/5;
		else
		    movingNode.x += (srcX - srcHx)/5;
		arrayNode.y += (srcY - srcAy)/5;
		redraw();
	    }
	}
	
	if (!nodeList.isEmpty())
	    nodeList.removeElementAt(0);
	if (!heapArray.isEmpty())
	    heapArray.removeElementAt(0);
	movingNode.setWeight(i);
	movingNode.x = srcX;
	movingNode.y = srcY;
	redraw();
	int destX = node.x;
	int destY = node.y;
	for (int k = 0; k < 3; k++) {
	    movingNode.x += (destX - srcX)/3;
	    redraw();
	}
	movingNode.x = destX;
	for (int k = 0; k < 5; k++) {
	    movingNode.y += (destY - srcY)/5;
	    redraw();
	}
	hideMovingNode();

	runningCom = null;
	outputList.addElement(node);
	redraw();
    }

    public void moveLast2First() {
	movingNode = (Node)nodeList.lastElement();
	runningCom = new ComBox(movingNode.x + 30, movingNode.y,
		"Moving last node to root...", Color.blue, Color.yellow,
		fixFont);
	if (nodeList.size() > 2) {
	    //remove this node from parent
	    int p = parent(nodeList.size()+1);
	    if ((nodeList.size()+1) == right(p))
	        ((Node)nodeList.elementAt(p-2)).setRightNode(null);
	    else
	        ((Node)nodeList.elementAt(p-2)).setLeftNode(null);
	}

	//remove this node
	nodeList.removeElementAt(nodeList.size()-1);

	//lastHeapArray
	Node lastHeapArray = (Node)heapArray.lastElement();
	

	// move node down;
	if (!nodeList.isEmpty()) {
	    movingNode.y += 17; lastHeapArray.y += 17; redraw();
	    movingNode.y += 17; lastHeapArray.y += 17; redraw();
	}

	int destHeapArrayX = drawingPanel.offset + 20;
	int srcHeapArrayX = lastHeapArray.x;
	int destX = drawingPanel.offset + 25;
	int srcX = movingNode.x;
	for (int i = 0; i < 5; i++) {
	    movingNode.x += (destX - srcX)/5;
	    lastHeapArray.x += (destHeapArrayX - srcHeapArrayX)/15; 
	    redraw();
	}
	movingNode.x = destX;
	int destY = ((Node)posnList.firstElement()).y;
	int srcY = movingNode.y;
	for (int i = 0; i < 5; i++) {
	destY = ((Node)posnList.firstElement()).y;
	    movingNode.y += (destY - srcY)/5;
	    lastHeapArray.x += (destHeapArrayX - srcHeapArrayX)/15; 
	    redraw();
	}
	movingNode.y = destY;
	destX = ((Node)posnList.firstElement()).x;
	srcX = movingNode.x;
	for (int i = 0; i < 5; i++) {
	    movingNode.x += (destX - srcX)/5;
	    lastHeapArray.x += (destHeapArrayX - srcHeapArrayX)/15; 
	    redraw();
	}
	movingNode.x = destX;
	lastHeapArray.x = destHeapArrayX;
	if (!nodeList.isEmpty()) {
	    lastHeapArray.y -= 17; redraw();
	    lastHeapArray.y -= 17;
	}
	heapArray.removeElementAt(heapArray.size()-1);
	heapArray.insertElementAt(lastHeapArray, 0);

	nodeList.insertElementAt(movingNode, 0);
	if (nodeList.size() > 1)
	    movingNode.setLeftNode((Node)nodeList.elementAt(1));
	if (nodeList.size() > 2)
	    movingNode.setRightNode((Node)nodeList.elementAt(2));
	
	hideMovingNode();
	runningCom = null;
	redraw();
    }

    public void restore(int i) {
	if (i < nodeList.size()) {
	    ((Node)nodeList.elementAt(i)).highlight = false;
	    ((Node)heapArray.elementAt(i)).highlight = false;
	}
    }

    public void highlight(int i) {
	if (i < nodeList.size()) {
	    ((Node)nodeList.elementAt(i)).highlight = true;
	    ((Node)heapArray.elementAt(i)).highlight = true;
	}
    }

    private void hideMovingNode() {
	movingNode = new Node(-1);
    }

    public void exchangeArrow(int i, int j) {
	// pre-condition: i+1 is parent, j+1 is child
	Node child = (Node)nodeList.elementAt(j);
	Node parent = (Node)nodeList.elementAt(i);

	exchanging = true;

	runningCom = new ComBox(child.x + 20, child.y - 10,
		"Swapping...", Color.blue, Color.yellow, fixFont);

	// check if is left or right child
	if ((j+1)==left(i+1)) {
	    // assign points: Point[] aPoints 
	    aPoints = new Point[2];
	    aPoints[0] = new Point(child.x + 2, child.y);
	    aPoints[1] = new Point(child.x + 2, parent.y + 15);
	    redraw();
	    aPoints = new Point[3];
	    aPoints[0] = new Point(child.x + 2, child.y);
	    aPoints[1] = new Point(child.x + 2, parent.y + 10);
	    aPoints[2] = new Point(parent.x - 8, parent.y + 10);
	    redraw();
	    aPoints = new Point[3];
	    aPoints[0] = new Point(child.x + 2, child.y);
	    aPoints[1] = new Point(child.x + 2, parent.y + 10);
	    aPoints[2] = new Point(parent.x, parent.y + 10);
	    redraw();
	    aPoints = new Point[2];
	    aPoints[0] = new Point(parent.x, parent.y + 10);
	    aPoints[1] = new Point(child.x + 6, parent.y + 10);
	    redraw();
	    aPoints = new Point[3];
	    aPoints[0] = new Point(parent.x, parent.y + 10);
	    aPoints[1] = new Point(child.x + 2, parent.y + 10);
	    aPoints[2] = new Point(child.x + 2, parent.y + 25);
	    redraw();
	    aPoints[0] = new Point(parent.x, parent.y + 10);
	    aPoints[1] = new Point(child.x + 2, parent.y + 10);
	    aPoints[2] = new Point(child.x + 2, child.y);
	    redraw();
	} else { // right child
	    aPoints = new Point[2];
	    aPoints[0] = new Point(child.x + 17, child.y);
	    aPoints[1] = new Point(child.x + 17, parent.y + 15);
	    redraw();
	    aPoints = new Point[3];
	    aPoints[0] = new Point(child.x + 17, child.y);
	    aPoints[1] = new Point(child.x + 17, parent.y + 10);
	    aPoints[2] = new Point(parent.x + 25, parent.y + 10);
	    redraw();
	    aPoints = new Point[3];
	    aPoints[0] = new Point(child.x + 17, child.y);
	    aPoints[1] = new Point(child.x + 17, parent.y + 10);
	    aPoints[2] = new Point(parent.x + 20, parent.y + 10);
	    redraw();
	    aPoints = new Point[2];
	    aPoints[0] = new Point(parent.x + 20, parent.y + 10);
	    aPoints[1] = new Point(child.x + 12, parent.y + 10);
	    redraw();
	    aPoints = new Point[3];
	    aPoints[0] = new Point(parent.x + 20, parent.y + 10);
	    aPoints[1] = new Point(child.x + 17, parent.y + 10);
	    aPoints[2] = new Point(child.x + 17, child.y - 10);
	    redraw();
	    aPoints[0] = new Point(parent.x + 20, parent.y + 10);
	    aPoints[1] = new Point(child.x + 17, parent.y + 10);
	    aPoints[2] = new Point(child.x + 17, child.y);
	    redraw();
	}

	Node array1 = (Node)heapArray.elementAt(i);
	Node array2 = (Node)heapArray.elementAt(j);
	Point orig1 = new Point(array1.x, array1.y);
	Point orig2 = new Point(array2.x, array2.y);
	boolean adj = (Math.abs(i-j) == 1);
	if (!adj) array1.y +=17; array2.y -= 17; redraw();
	if (!adj) array1.y +=17; array2.y -= 17; redraw();

	for (int k = 0; k < 4; k++) {
	    array1.x += (orig2.x - orig1.x)/4;
	    array2.x += (orig1.x - orig2.x)/4;
	    redraw();
	}
	array1.x = orig2.x;
	array2.x = orig1.x;
	if (!adj) array1.y -=17; array2.y += 17; redraw();

	int tmpWeight = array1.getWeight();
	array1.setWeight(array2.getWeight());
	array2.setWeight(tmpWeight);
	array1.x = orig1.x; array1.y = orig1.y;
	array2.x = orig2.x; array2.y = orig2.y;
	runningCom = null;
	redraw();

	exchanging = false;
    }

    public void input2heap() {
	int inputNum = inputList.size();
	    Node node = (Node)inputList.firstElement();
	    delFirstInput();
	    movingNode = node;
	    movingNode.y -= 17; redraw();

	    Node newNode = new Node(movingNode.getWeight());
	    newNode.x = drawingPanel.offset + 20 + heapArray.size() * 22;
	    movingNode.y = bottomMostPosn(posn) + 50;
	    redraw();
	runningCom = new ComBox(newNode.x + 100, node.y,
		"Inserting input into heap...", Color.blue, Color.yellow,
		fixFont);

	    Node arrayNode = new Node(movingNode.getWeight());
	    arrayNode.x = movingNode.x;
	    arrayNode.y = movingNode.y;
	    heapArray.addElement(arrayNode);

	    Node destNode = (Node)posnList.elementAt(nodeList.size());