Skip to content

Commit 18a5148

Browse files
nikitap492nikitap492
committed
Refactored HeapSort
1 parent 9491b45 commit 18a5148

1 file changed

Lines changed: 94 additions & 139 deletions

File tree

‎Sorts/src/sort/HeapSort.java‎

Lines changed: 94 additions & 139 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,10 @@
11
package sort;
22

3-
import java.util.Scanner;
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
import static sort.SortUtils.*;
48

59
/**
610
* Heap Sort Algorithm
@@ -9,156 +13,108 @@
913
* @author Unknown
1014
*
1115
*/
12-
public class HeapSort {
13-
/** Array to store heap */
14-
private int[] heap;
15-
/** The size of the heap */
16-
private int size;
17-
18-
/**
19-
* Constructor
20-
*
21-
* @param heap array of unordered integers
22-
*/
23-
public HeapSort(int[] heap) {
24-
this.setHeap(heap);
25-
this.setSize(heap.length);
26-
}
16+
public class HeapSort implements SortAlgorithm {
2717

28-
/**
29-
* Setter for variable size
30-
*
31-
* @param length new size
32-
*/
33-
private void setSize(int length) {
34-
this.size = length;
35-
}
3618

37-
/**
38-
* Setter for variable heap
39-
*
40-
* @param heap array of unordered elements
41-
*/
42-
private void setHeap(int[] heap) {
43-
this.heap = heap;
44-
}
19+
private static class Heap<T extends Comparable<T>> {
20+
/** Array to store heap */
21+
private T[] heap;
4522

46-
/**
47-
* Swaps index of first with second
48-
*
49-
* @param first First index to switch
50-
* @param second Second index to switch
51-
*/
52-
private void swap(int first, int second) {
53-
int temp = this.heap[first];
54-
this.heap[first] = this.heap[second];
55-
this.heap[second] = temp;
56-
}
23+
/**
24+
* Constructor
25+
*
26+
* @param heap array of unordered integers
27+
*/
28+
public Heap(T[] heap) {
29+
this.heap = heap;
30+
}
5731

58-
/**
59-
* Heapifies subtree from top as root to last as last child
60-
*
61-
* @param rootIndex index of root
62-
* @param lastChild index of last child
63-
*/
64-
private void heapSubtree(int rootIndex, int lastChild) {
65-
int leftIndex = rootIndex * 2 + 1;
66-
int rightIndex = rootIndex * 2 + 2;
67-
int root = this.heap[rootIndex];
68-
if (rightIndex <= lastChild) { // if has right and left children
69-
int left = this.heap[leftIndex];
70-
int right = this.heap[rightIndex];
71-
if (left < right && left < root) {
72-
this.swap(leftIndex, rootIndex);
73-
this.heapSubtree(leftIndex, lastChild);
74-
} else if (right < root) {
75-
this.swap(rightIndex, rootIndex);
76-
this.heapSubtree(rightIndex, lastChild);
32+
/**
33+
* Heapifies subtree from top as root to last as last child
34+
*
35+
* @param rootIndex index of root
36+
* @param lastChild index of last child
37+
*/
38+
private void heapSubtree(int rootIndex, int lastChild) {
39+
int leftIndex = rootIndex * 2 + 1;
40+
int rightIndex = rootIndex * 2 + 2;
41+
T root = heap[rootIndex];
42+
if (rightIndex <= lastChild) { // if has right and left children
43+
T left = heap[leftIndex];
44+
T right = heap[rightIndex];
45+
if (less(left, right) && less(left, root)) {
46+
swap(heap, leftIndex, rootIndex);
47+
heapSubtree(leftIndex, lastChild);
48+
} else if (less(right, root)) {
49+
swap(heap, rightIndex, rootIndex);
50+
heapSubtree(rightIndex, lastChild);
51+
}
52+
} else if (leftIndex <= lastChild) { // if no right child, but has left child
53+
T left = heap[leftIndex];
54+
if (less(left, root)) {
55+
swap(heap, leftIndex, rootIndex);
56+
heapSubtree(leftIndex, lastChild);
57+
}
7758
}
78-
} else if (leftIndex <= lastChild) { // if no right child, but has left child
79-
int left = this.heap[leftIndex];
80-
if (left < root) {
81-
this.swap(leftIndex, rootIndex);
82-
this.heapSubtree(leftIndex, lastChild);
59+
}
60+
61+
62+
/**
63+
* Makes heap with root as root
64+
*
65+
* @param root index of root of heap
66+
*/
67+
private void makeMinHeap(int root) {
68+
int leftIndex = root * 2 + 1;
69+
int rightIndex = root * 2 + 2;
70+
boolean hasLeftChild = leftIndex < heap.length;
71+
boolean hasRightChild = rightIndex < heap.length;
72+
if (hasRightChild) { //if has left and right
73+
makeMinHeap(leftIndex);
74+
makeMinHeap(rightIndex);
75+
heapSubtree(root, heap.length - 1);
76+
} else if (hasLeftChild) {
77+
heapSubtree(root, heap.length - 1);
8378
}
8479
}
85-
}
8680

87-
/**
88-
* Makes heap with root as root
89-
*
90-
* @param root index of root of heap
91-
*/
92-
private void makeMinHeap(int root) {
93-
int leftIndex = root * 2 + 1;
94-
int rightIndex = root * 2 + 2;
95-
boolean hasLeftChild = leftIndex < this.heap.length;
96-
boolean hasRightChild = rightIndex < this.heap.length;
97-
if (hasRightChild) { //if has left and right
98-
this.makeMinHeap(leftIndex);
99-
this.makeMinHeap(rightIndex);
100-
this.heapSubtree(root, this.heap.length - 1);
101-
} else if (hasLeftChild) {
102-
this.heapSubtree(root, this.heap.length - 1);
81+
/**
82+
* Gets the root of heap
83+
*
84+
* @return root of heap
85+
*/
86+
private T getRoot(int size) {
87+
swap(heap, 0, size);
88+
heapSubtree(0, size - 1);
89+
return heap[size]; // return old root
10390
}
104-
}
10591

106-
/**
107-
* Gets the root of heap
108-
*
109-
* @return root of heap
110-
*/
111-
private int getRoot() {
112-
this.swap(0, this.size - 1);
113-
this.size--;
114-
this.heapSubtree(0, this.size - 1);
115-
return this.heap[this.size]; // return old root
116-
}
11792

118-
/**
119-
* Sorts heap with heap sort; displays ordered elements to console.
120-
*
121-
* @return sorted array of sorted elements
122-
*/
123-
public final int[] sort() {
124-
this.makeMinHeap(0); // make min heap using index 0 as root.
125-
int[] sorted = new int[this.size];
126-
int index = 0;
127-
while (this.size > 0) {
128-
int min = this.getRoot();
129-
sorted[index] = min;
130-
index++;
131-
}
132-
return sorted;
93+
94+
95+
13396
}
13497

135-
/**
136-
* Gets input to sort
137-
*
138-
* @return unsorted array of integers to sort
139-
*/
140-
public static int[] getInput() {
141-
final int numElements = 6;
142-
int[] unsorted = new int[numElements];
143-
Scanner input = new Scanner(System.in);
144-
System.out.println("Enter any 6 Numbers for Unsorted Array : ");
145-
for (int i = 0; i < numElements; i++) {
146-
unsorted[i] = input.nextInt();
147-
}
148-
input.close();
149-
return unsorted;
98+
@Override
99+
public <T extends Comparable<T>> T[] sort(T[] unsorted) {
100+
return sort(Arrays.asList(unsorted)).toArray(unsorted);
150101
}
151102

152-
/**
153-
* Prints elements in heap
154-
*
155-
* @param heap array representing heap
156-
*/
157-
public static void printData(int[] heap) {
158-
System.out.println("Sorted Elements:");
159-
for (int i = 0; i < heap.length; i++) {
160-
System.out.print(" " + heap[i] + " ");
103+
@Override
104+
public <T extends Comparable<T>> List<T> sort(List<T> unsorted) {
105+
int size = unsorted.size();
106+
107+
@SuppressWarnings("unchecked")
108+
Heap<T> heap = new Heap<>(unsorted.toArray((T[]) new Comparable[unsorted.size()]));
109+
110+
heap.makeMinHeap(0); // make min heap using index 0 as root.
111+
List<T> sorted = new ArrayList<>(size);
112+
while (size > 0) {
113+
T min = heap.getRoot(--size);
114+
sorted.add(min);
161115
}
116+
117+
return sorted;
162118
}
163119

164120
/**
@@ -167,10 +123,9 @@ public static void printData(int[] heap) {
167123
* @param args the command line arguments
168124
*/
169125
public static void main(String[] args) {
170-
int[] heap = getInput();
171-
HeapSort data = new HeapSort(heap);
172-
int[] sorted = data.sort();
173-
printData(sorted);
126+
Integer[] heap = {4, 23, 6, 78, 1, 54, 231, 9, 12};
127+
HeapSort heapSort = new HeapSort();
128+
print(heapSort.sort(heap));
174129
}
175130

176131
}

0 commit comments

Comments
 (0)