Skip to content

Commit 3ffd887

Browse files
vbohushvbohush
committed
begin heap sort
1 parent c1b59ff commit 3ffd887

File tree

4 files changed

+144
-3
lines changed

4 files changed

+144
-3
lines changed

‎src/net/bohush/sorting/Heap.java‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
package net.bohush.sorting;
2+
3+
class Heap<E extends Comparable<E>> {
4+
private java.util.ArrayList<E> heapList = new java.util.ArrayList<E>();
5+
6+
/** Create a default heap */
7+
public Heap() {
8+
}
9+
10+
/** Create a heap from an array of objects */
11+
public Heap(E[] objects) {
12+
for (int i = 0; i < objects.length; i++)
13+
add(objects[i]);
14+
}
15+
16+
/** Add a new object into the heap */
17+
public void add(E newObject) {
18+
heapList.add(newObject); // Append to the heap
19+
int currentIndex = heapList.size() - 1; // The index of the last node
20+
21+
while (currentIndex > 0) {
22+
int parentIndex = (currentIndex - 1) / 2;
23+
// Swap if the current object is greater than its parent
24+
if (heapList.get(currentIndex).compareTo(heapList.get(parentIndex)) > 0) {
25+
E temp = heapList.get(currentIndex);
26+
heapList.set(currentIndex, heapList.get(parentIndex));
27+
heapList.set(parentIndex, temp);
28+
} else
29+
break; // the tree is a heap now
30+
31+
currentIndex = parentIndex;
32+
}
33+
}
34+
35+
/** Remove the root from the heap */
36+
public E remove() {
37+
if (heapList.size() == 0)
38+
return null;
39+
40+
E removedObject = heapList.get(0);
41+
heapList.set(0, heapList.get(heapList.size() - 1));
42+
heapList.remove(heapList.size() - 1);
43+
44+
int currentIndex = 0;
45+
while (currentIndex < heapList.size()) {
46+
int leftChildIndex = 2 * currentIndex + 1;
47+
int rightChildIndex = 2 * currentIndex + 2;
48+
49+
// Find the maximum between two children
50+
if (leftChildIndex >= heapList.size())
51+
break; // The tree is a heap
52+
int maxIndex = leftChildIndex;
53+
if (rightChildIndex < heapList.size()) {
54+
if (heapList.get(maxIndex).compareTo(heapList.get(rightChildIndex)) < 0) {
55+
maxIndex = rightChildIndex;
56+
}
57+
}
58+
59+
// Swap if the current node is less than the maximum
60+
if (heapList.get(currentIndex).compareTo(heapList.get(maxIndex)) < 0) {
61+
E temp = heapList.get(maxIndex);
62+
heapList.set(maxIndex, heapList.get(currentIndex));
63+
heapList.set(currentIndex, temp);
64+
currentIndex = maxIndex;
65+
} else
66+
break; // The tree is a heap
67+
}
68+
69+
return removedObject;
70+
}
71+
72+
/** Get the number of nodes in the tree */
73+
public int getSize() {
74+
return heapList.size();
75+
}
76+
}

‎src/net/bohush/sorting/HeapSortPanel.java‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package net.bohush.sorting;
2+
3+
import java.awt.Color;
4+
import java.awt.Graphics;
5+
6+
public class HeapSortPanel extends SortPanel {
7+
private static final long serialVersionUID = 1L;
8+
private int redColumn = -1;
9+
private int greenColumn = -1;
10+
11+
public HeapSortPanel(String name, int[] list, int sleepTime) {
12+
super(name, list, sleepTime);
13+
}
14+
15+
@Override
16+
public void run() {
17+
try {
18+
19+
Heap<Integer> heap = new Heap<Integer>();
20+
21+
// Add elements to the heap
22+
for (int i = 0; i < list.length; i++) {
23+
heap.add(list[i]);
24+
Thread.sleep(10 * sleepTime);
25+
repaint();
26+
}
27+
28+
// Remove elements from the heap
29+
for (int i = list.length - 1; i >= 0; i--) {
30+
list[i] = heap.remove();
31+
Thread.sleep(10 * sleepTime);
32+
repaint();
33+
}
34+
35+
36+
} catch (InterruptedException e) {
37+
}
38+
repaint();
39+
}
40+
41+
@Override
42+
protected void paintComponent(Graphics g) {
43+
super.paintComponent(g);
44+
int columnWidth = (getWidth() - 4 * BORDER_WIDTH) / size;
45+
int columnHeight = (getHeight() - 4 * BORDER_WIDTH) / size;
46+
for (int i = (greenColumn == -1 ? 0 : greenColumn); i < list.length; i++) {
47+
g.setColor(Color.WHITE);
48+
g.fillRect(2 * BORDER_WIDTH + columnWidth * i, getHeight() - list[i] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[i] * columnHeight);
49+
g.setColor(Color.BLACK);
50+
g.drawRect(2 * BORDER_WIDTH + columnWidth * i, getHeight() - list[i] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[i] * columnHeight);
51+
}
52+
for (int i = 0; i <= greenColumn; i++) {
53+
g.setColor(Color.GREEN);
54+
g.fillRect(2 * BORDER_WIDTH + columnWidth * i, getHeight() - list[i] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[i] * columnHeight);
55+
g.setColor(Color.BLACK);
56+
g.drawRect(2 * BORDER_WIDTH + columnWidth * i, getHeight() - list[i] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[i] * columnHeight);
57+
}
58+
if(redColumn != -1) {
59+
g.setColor(Color.RED);
60+
g.fillRect(2 * BORDER_WIDTH + columnWidth * redColumn, getHeight() - list[redColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[redColumn] * columnHeight);
61+
g.setColor(Color.BLACK);
62+
g.drawRect(2 * BORDER_WIDTH + columnWidth * redColumn, getHeight() - list[redColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[redColumn] * columnHeight);
63+
}
64+
}
65+
}

‎src/net/bohush/sorting/Main.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,7 @@ public Main() {
3030
sortPanels[2] = new BubbleSortPanel(" Bubble Sort ", list, sleepTime);
3131
sortPanels[3] = new QuickSortPanel(" Quick Sort ", list, sleepTime);
3232
sortPanels[4] = new MergeSortPanel(" Merge Sort ", list, sleepTime);
33-
sortPanels[5] = new QuickSortPanel(" Quick Sort ", list, sleepTime);
33+
sortPanels[5] = new HeapSortPanel(" Heap Sort ", list, sleepTime);
3434
/*sortPanels[6] = new QuickSortPanel(" Quick Sort ", list, sleepTime);
3535
sortPanels[7] = new QuickSortPanel(" Quick Sort ", list, sleepTime);
3636
sortPanels[8] = new QuickSortPanel(" Quick Sort ", list, sleepTime);
@@ -46,7 +46,7 @@ public static void main(String[] args) {
4646
JFrame frame = new JFrame("Sorting Algorithm Animations");
4747
JApplet applet = new Main();
4848
frame.add(applet);
49-
//frame.setUndecorated(true);
49+
frame.setUndecorated(true);
5050
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
5151
frame.pack();
5252
frame.setLocationRelativeTo(null);

‎src/net/bohush/sorting/SortPanel.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111
public abstract class SortPanel extends JPanel implements Runnable {
1212
private static final long serialVersionUID = 1L;
1313
protected static final int BORDER_WIDTH = 10;
14-
private static final Dimension PREFFERED_DIMENSION = new Dimension(340, 340);
14+
private static final Dimension PREFFERED_DIMENSION = new Dimension(640, 540);
1515
protected int size;
1616
protected int[] list;
1717
protected int sleepTime;

0 commit comments

Comments
 (0)