Tjena, jag leker lite med Binary Heap men har fastnat lite i tankeverksamheten. Jag har med hjälp av tutorials lyckats skapa och fylla denna Heapen med rätt siffror.
Arrayen är tänkt att se ut såhär när den linjära lösningen är implementerad.
Värde: 1, 3, 2,12, 6,4, 8, 15,14,9, 7, 5, 11, 13, 10
Plats: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
Koden ser ut enligt följande och något säger mig att lösningen är enkel men jag kan inte komma på någon lösning.
Kod:
public class Main {
public static void main(String[] args) throws IOException {
//10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, 2
BinaryHeap bh = new BinaryHeap(15);
bh.insert(10);
bh.insert(12);
bh.insert(1);
bh.insert(14);
bh.insert(6);
bh.insert(5);
bh.insert(8);
bh.insert(15);
bh.insert(3);
bh.insert(9);
bh.insert(7);
bh.insert(4);
bh.insert(11);
bh.insert(13);
bh.insert(2);
//System.out.println(bh.deleteMin());
//System.out.println(bh.isFull());
//System.out.println("Empty status = "+ bh.isEmpty());
//bh.makeEmpty();
bh.printHeap();
System.out.println(bh.findMin());
}
}
/** Class BinaryHeap **/
class BinaryHeap
{
/** The number of children each node has **/
private static final int d = 2;
private int heapSize;
private int[] heap ;
// Constructor **/
public BinaryHeap(int capacity)
{
heapSize = 0;
heap = new int[capacity + 1];
Arrays.fill(heap, -1);
}
// Function to check if heap is empty **/
public boolean isEmpty( )
{
return heapSize == 0;
}
// Check if heap is full
public boolean isFull( )
{
return heapSize == heap.length;
}
/** Clear heap */
public void makeEmpty( )
{
heapSize = 0;
}
/** Function to get index parent of i **/
private int parent(int i)
{
return (i - 1)/d;
}
/** Function to get index of k th child of i **/
private int kthChild(int i, int k)
{
return d * i + k;
}
/** Function to insert element */
public void insert(int x)
{
if (isFull( ) )
throw new NoSuchElementException("Overflow Exception");
/** Percolate up **/
heap[heapSize++] = x;
heapifyDown(heapSize - 1);
}
/** Function to find least element **/
public int findMin( )
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
return heap[0];
}
/** Function to delete min element **/
public int deleteMin()
{
int keyItem = heap[0];
delete(0);
return keyItem;
}
/** Function to delete element at an index **/
public int delete(int ind)
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
int keyItem = heap[ind];
heap[ind] = heap[heapSize - 1];
heapSize--;
heapifyDown(ind);
return keyItem;
}
/** Function heapifyUp **/
private void heapifyUp(int childInd)
{
int tmp = heap[childInd];
while (childInd > 0 && tmp < heap[parent(childInd)])
{
heap[childInd] = heap[ parent(childInd) ];
childInd = parent(childInd);
}
heap[childInd] = tmp;
}
/** Function heapifyDown **/
private void heapifyDown(int ind)
{
int child;
int tmp = heap[ ind ];
while (kthChild(ind, 1) < heapSize)
{
child = minChild(ind);
if (heap[child] < tmp)
heap[ind] = heap[child];
else
break;
ind = child;
}
heap[ind] = tmp;
}
/** Function to get smallest child **/
private int minChild(int ind)
{
int bestChild = kthChild(ind, 1);
int k = 2;
int pos = kthChild(ind, k);
while ((k <= d) && (pos < heapSize))
{
if (heap[pos] < heap[bestChild])
bestChild = pos;
pos = kthChild(ind, k++);
}
return bestChild;
}
/** Function to print heap **/
public void printHeap()
{
System.out.print("\nHeap = ");
for (int i = 0; i < heapSize; i++)
System.out.print(heap[i] +" ");
System.out.println();
}
}
