ex5.java

java实现最小堆操作

import java.awt.*;
import java.awt.event.*;
import java.util.Vector;

import javax.swing.*;

public class Ex5 extends JFrame implements ActionListener
{

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	JTextField field1;
	JTextField field2;
    JButton buttonAppend;
    JButton buttonDelete;
    JButton buttonelem[][];
 
    Container container;
    int Column=1;
    int count=1;
    int countleft=1;
    Heap heapNow;
    Vector<Integer> value=new Vector<Integer>(1);
	
	Ex5()
    {
        super("数据结构实验5--最小堆操作040824409解旻");
        field1 = new JTextField(5);
        field2=new JTextField(3);
        buttonAppend = new JButton("添加新元素");
        buttonDelete = new JButton("删除堆顶");

        JPanel jpanel = new JPanel();
        jpanel.setLayout(new GridLayout(1, 4, 15, 0));
        jpanel.add(new JLabel("待添加的整数[-999, 999]:"));
        jpanel.add(field1);
        jpanel.add(buttonAppend);
        buttonAppend.addActionListener(this);
        jpanel.add(buttonDelete);
        buttonDelete.addActionListener(this);
       
        container = getContentPane();
        container.add(jpanel, "North");
        
        container.add(new JLabel("按照最小堆算法进行操作,操作结果将在堆中显示"), "South");
        buttonAppend.setEnabled(true);
        buttonDelete.setEnabled(false);
        setSize(1020, 400);
        setDefaultCloseOperation(3);
        setVisible(true);

    }

    public void actionPerformed(ActionEvent actionevent)
    {
        JButton jbutton = (JButton)actionevent.getSource();
        if(jbutton == buttonAppend)
        {
            String s = field1.getText();
            s = s.trim();
            int num = 0;
            try
            {
                num = Integer.parseInt(s);
            }
            catch(NumberFormatException numberformatexception)
            {
                JOptionPane.showMessageDialog(this, "您所输入的内容不能转换成整数，请修改");
                return;
            }
            if(num < -999 || num > 999)
            {
                JOptionPane.showMessageDialog(this, "您所输的内容不在[-999, 999]之间,请修改");
                return;
            }
            
            if(count==31)
            	buttonAppend.setEnabled(false);
            
            if(count==countleft*2){
            	countleft=count;
            	Column++;
            }
            
            value.setSize((int)(Math.pow(2, (double)Column)-1));
            value.set(count-1, num);
            
            heapNow=new Heap(value);
            heapNow.HeapSort();
            count++;
            showHeap(heapNow);
            
            buttonDelete.setEnabled(true);
            field1.requestFocus();
            field1.selectAll();
            return;
        }
        if(jbutton == buttonDelete)
        {
        	if(count-1==countleft){
            	countleft=countleft/2;
            	Column--;
            }
        	count--;
        	if(count==1){
        		container.add(new JButton("Empty Heap"),"Center");
        		buttonDelete.setEnabled(false);
        		container.validate();
        		countleft=1;
        		Column=1;
        		return;
        	}
        	heapNow.HeapDel();
            showHeap(heapNow);
            
            buttonAppend.setEnabled(true);
            return;
        } else
        {
            return;
        }
    }
    
    public void showHeap(Heap heap){
    	 JPanel ajpanel[] = new JPanel[Column];
         for(int i = 0; i < Column ; i++){
         	ajpanel[i] = new JPanel();
         	ajpanel[i].setLayout(new GridLayout(1,(int)(Math.pow(2, (double)i))));
         }
        
     
        
         buttonelem = new JButton[Column][];
         int j = 1;
         for(int k = 0; k <Column ; k++)
         {
             buttonelem[k] = new JButton[j];
             for(int l = 0; l < j; l++)
             {
                 buttonelem[k][l] = new JButton();
                 buttonelem[k][l].setEnabled(false);
                 ajpanel[k].add(buttonelem[k][l]);
                 try{
                	 if(heap.val.get((int)(Math.pow(2, (double)k)-1+l))!=null)
                		 buttonelem[k][l].setText(String.valueOf(heap.val.get((int)(Math.pow(2, (double)k)-1+l))));
                 }catch(ArrayIndexOutOfBoundsException exp){
                	 
                 }
             }

             j *= 2;
         }
         JPanel jpanel1 = new JPanel();
         
         jpanel1.setLayout(new GridLayout(Column, 1));
         for(int i = 0; i < Column; i++)
             jpanel1.add(ajpanel[i]);
         JScrollPane jscrollpane = new JScrollPane(jpanel1);
         
         container.add(jscrollpane, "Center");
         container.validate();
    	
    }



    public static void main(String args[])
    {
        new Ex5();
    }  
    
}

class Heap{
	Vector<Integer> val;
	Heap(Vector<Integer>value){
		val=value;
	}
	
	public void HeapAdjust(int s,int m){
		int rc=val.get(s-1);
		for(int j=2*s;j<=m;j*=2){
			if(j<m&&val.get(j-1)>val.get(j))
				++j;
			if(rc<val.get(j-1))
				break;
			val.set(s-1, val.get(j-1));
			s=j;
		}
		val.set(s-1, new Integer(rc));
	}
	
	public void HeapSort(){
		int tot=0;
		for(int i=0;i<val.size();i++){
			if(val.get(i)!=null)
				tot++;
			
		}
		
		
		for(int i=tot/2;i>0;--i){
			HeapAdjust(i,tot);
		}
	}
	
	public void HeapDel(){
		int tot=0;
		for(int i=0;i<val.size();i++){
			if(val.get(i)!=null)
				tot++;
			
		}
		val.set(0, val.get(tot-1));
		val.setSize(tot-1);
		
		HeapAdjust(1,tot-1);

	}
	
}