1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711
| /*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package aaaalgorithme;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/***********************************************************************
* File: FibonacciHeap.java
* Author: Keith Schwarz (htiek@cs.stanford.edu)
*
* An implementation of a priority queue backed by a Fibonacci heap,
* as described by Fredman and Tarjan. Fibonacci heaps are interesting
* theoretically because they have asymptotically good runtime guarantees
* for many operations. In particular, insert, peek, and decrease-key all
* run in amortized O(1) time. dequeueMin and delete each run in amortized
* O(lg n) time. This allows algorithms that rely heavily on decrease-key
* to gain significant performance boosts. For example, Dijkstra's algorithm
* for single-source shortest paths can be shown to run in O(m + n lg n) using
* a Fibonacci heap, compared to O(m lg n) using a standard binary or binomial
* heap.
*
* Internally, a Fibonacci heap is represented as a circular, doubly-linked
* list of trees obeying the min-heap property. Each node stores pointers
* to its parent (if any) and some arbitrary child. Additionally, every
* node stores its degree (the number of children it has) and whether it
* is a "marked" node. Finally, each Fibonacci heap stores a pointer to
* the tree with the minimum value.
*
* To insert a node into a Fibonacci heap, a singleton tree is created and
* merged into the rest of the trees. The merge operation works by simply
* splicing together the doubly-linked lists of the two trees, then updating
* the min pointer to be the smaller of the minima of the two heaps. Peeking
* at the smallest element can therefore be accomplished by just looking at
* the min element. All of these operations complete in O(1) time.
*
* The tricky operations are dequeueMin and decreaseKey. dequeueMin works
* by removing the root of the tree containing the smallest element, then
* merging its children with the topmost roots. Then, the roots are scanned
* and merged so that there is only one tree of each degree in the root list.
* This works by maintaining a dynamic array of trees, each initially null,
* pointing to the roots of trees of each dimension. The list is then scanned
* and this array is populated. Whenever a conflict is discovered, the
* appropriate trees are merged together until no more conflicts exist. The
* resulting trees are then put into the root list. A clever analysis using
* the potential method can be used to show that the amortized cost of this
* operation is O(lg n), see "Introduction to Algorithms, Second Edition" by
* Cormen, Rivest, Leiserson, and Stein for more details.
*
* The other hard operation is decreaseKey, which works as follows. First, we
* update the key of the node to be the new value. If this leaves the node
* smaller than its parent, we're done. Otherwise, we cut the node from its
* parent, add it as a root, and then mark its parent. If the parent was
* already marked, we cut that node as well, recursively mark its parent,
* and continue this process. This can be shown to run in O(1) amortized time
* using yet another clever potential function. Finally, given this function,
* we can implement delete by decreasing a key to -\infty, then calling
* dequeueMin to extract it.
*/
import java.util.*; // For ArrayList
/**
* A class representing a Fibonacci heap.
*
* @param T The type of elements to store in the heap.
* @author Keith Schwarz (htiek@cs.stanford.edu)
*/
public final class FibonacciHeap<T> {
/* In order for all of the Fibonacci heap operations to complete in O(1),
* clients need to have O(1) access to any element in the heap. We make
* this work by having each insertion operation produce a handle to the
* node in the tree. In actuality, this handle is the node itself, but
* we guard against external modification by marking the internal fields
* private.
*/
public static final class Entry<T> {
private int mDegree = 0; // Number of children
private boolean mIsMarked = false; // Whether this node is marked
private Entry<T> mNext; // Next and previous elements in the list
private Entry<T> mPrev;
private Entry<T> mParent; // Parent in the tree, if any.
private Entry<T> mChild; // Child node, if any.
private T mElem; // Element being stored here
private double mPriority; // Its priority
/**
* Returns the element represented by this heap entry.
*
* @return The element represented by this heap entry.
*/
public T getValue() {
return mElem;
}
/**
* Sets the element associated with this heap entry.
*
* @param value The element to associate with this heap entry.
*/
public void setValue(T value) {
mElem = value;
}
/**
* Returns the priority of this element.
*
* @return The priority of this element.
*/
public double getPriority() {
return mPriority;
}
/**
* Constructs a new Entry that holds the given element with the indicated
* priority.
*
* @param elem The element stored in this node.
* @param priority The priority of this element.
*/
private Entry(T elem, double priority) {
mNext = mPrev = this;
mElem = elem;
mPriority = priority;
}
}
/* Pointer to the minimum element in the heap. */
private Entry<T> mMin = null;
/* Cached size of the heap, so we don't have to recompute this explicitly. */
private int mSize = 0;
/**
* Inserts the specified element into the Fibonacci heap with the specified
* priority. Its priority must be a valid double, so you cannot set the
* priority to NaN.
*
* @param value The value to insert.
* @param priority Its priority, which must be valid.
* @return An Entry representing that element in the tree.
*/
public Entry<T> enqueue(T value, double priority) {
checkPriority(priority);
/* Create the entry object, which is a circularly-linked list of length
* one.
*/
Entry<T> result = new Entry<T>(value, priority);
/* Merge this singleton list with the tree list. */
mMin = mergeLists(mMin, result);
/* Increase the size of the heap; we just added something. */
++mSize;
/* Return the reference to the new element. */
return result;
}
/**
* Returns an Entry object corresponding to the minimum element of the
* Fibonacci heap, throwing a NoSuchElementException if the heap is
* empty.
*
* @return The smallest element of the heap.
* @throws NoSuchElementException If the heap is empty.
*/
public Entry<T> min() {
if (isEmpty())
throw new NoSuchElementException("Heap is empty.");
return mMin;
}
/**
* Returns whether the heap is empty.
*
* @return Whether the heap is empty.
*/
public boolean isEmpty() {
return mMin == null;
}
/**
* Returns the number of elements in the heap.
*
* @return The number of elements in the heap.
*/
public int size() {
return mSize;
}
/**
* Given two Fibonacci heaps, returns a new Fibonacci heap that contains
* all of the elements of the two heaps. Each of the input heaps is
* destructively modified by having all its elements removed. You can
* continue to use those heaps, but be aware that they will be empty
* after this call completes.
*
* @param one The first Fibonacci heap to merge.
* @param two The second Fibonacci heap to merge.
* @return A new FibonacciHeap containing all of the elements of both
* heaps.
*/
public static <T> FibonacciHeap<T> merge(FibonacciHeap<T> one, FibonacciHeap<T> two) {
/* Create a new FibonacciHeap to hold the result. */
FibonacciHeap<T> result = new FibonacciHeap<T>();
/* Merge the two Fibonacci heap root lists together. This helper function
* also computes the min of the two lists, so we can store the result in
* the mMin field of the new heap.
*/
result.mMin = mergeLists(one.mMin, two.mMin);
/* The size of the new heap is the sum of the sizes of the input heaps. */
result.mSize = one.mSize + two.mSize;
/* Clear the old heaps. */
one.mSize = two.mSize = 0;
one.mMin = null;
two.mMin = null;
/* Return the newly-merged heap. */
return result;
}
/**
* Dequeues and returns the minimum element of the Fibonacci heap. If the
* heap is empty, this throws a NoSuchElementException.
*
* @return The smallest element of the Fibonacci heap.
* @throws NoSuchElementException If the heap is empty.
*/
public Entry<T> dequeueMin() {
/* Check for whether we're empty. */
if (isEmpty())
throw new NoSuchElementException("Heap is empty.");
/* Otherwise, we're about to lose an element, so decrement the number of
* entries in this heap.
*/
--mSize;
/* Grab the minimum element so we know what to return. */
Entry<T> minElem = mMin;
/* Now, we need to get rid of this element from the list of roots. There
* are two cases to consider. First, if this is the only element in the
* list of roots, we set the list of roots to be null by clearing mMin.
* Otherwise, if it's not null, then we write the elements next to the
* min element around the min element to remove it, then arbitrarily
* reassign the min.
*/
if (mMin.mNext == mMin) { // Case one
mMin = null;
}
else { // Case two
mMin.mPrev.mNext = mMin.mNext;
mMin.mNext.mPrev = mMin.mPrev;
mMin = mMin.mNext; // Arbitrary element of the root list.
}
/* Next, clear the parent fields of all of the min element's children,
* since they're about to become roots. Because the elements are
* stored in a circular list, the traversal is a bit complex.
*/
if (minElem.mChild != null) {
/* Keep track of the first visited node. */
Entry<?> curr = minElem.mChild;
do {
curr.mParent = null;
/* Walk to the next node, then stop if this is the node we
* started at.
*/
curr = curr.mNext;
} while (curr != minElem.mChild);
}
/* Next, splice the children of the root node into the topmost list,
* then set mMin to point somewhere in that list.
*/
mMin = mergeLists(mMin, minElem.mChild);
/* If there are no entries left, we're done. */
if (mMin == null) return minElem;
/* Next, we need to coalsce all of the roots so that there is only one
* tree of each degree. To track trees of each size, we allocate an
* ArrayList where the entry at position i is either null or the
* unique tree of degree i.
*/
List<Entry<T>> treeTable = new ArrayList<Entry<T>>();
/* We need to traverse the entire list, but since we're going to be
* messing around with it we have to be careful not to break our
* traversal order mid-stream. One major challenge is how to detect
* whether we're visiting the same node twice. To do this, we'll
* spent a bit of overhead adding all of the nodes to a list, and
* then will visit each element of this list in order.
*/
List<Entry<T>> toVisit = new ArrayList<Entry<T>>();
/* To add everything, we'll iterate across the elements until we
* find the first element twice. We check this by looping while the
* list is empty or while the current element isn't the first element
* of that list.
*/
for (Entry<T> curr = mMin; toVisit.isEmpty() || toVisit.get(0) != curr; curr = curr.mNext)
toVisit.add(curr);
/* Traverse this list and perform the appropriate unioning steps. */
for (Entry<T> curr: toVisit) {
/* Keep merging until a match arises. */
while (true) {
/* Ensure that the list is long enough to hold an element of this
* degree.
*/
while (curr.mDegree >= treeTable.size())
treeTable.add(null);
/* If nothing's here, we're can record that this tree has this size
* and are done processing.
*/
if (treeTable.get(curr.mDegree) == null) {
treeTable.set(curr.mDegree, curr);
break;
}
/* Otherwise, merge with what's there. */
Entry<T> other = treeTable.get(curr.mDegree);
treeTable.set(curr.mDegree, null); // Clear the slot
/* Determine which of the two trees has the smaller root, storing
* the two tree accordingly.
*/
Entry<T> min = (other.mPriority < curr.mPriority)? other : curr;
Entry<T> max = (other.mPriority < curr.mPriority)? curr : other;
/* Break max out of the root list, then merge it into min's child
* list.
*/
max.mNext.mPrev = max.mPrev;
max.mPrev.mNext = max.mNext;
/* Make it a singleton so that we can merge it. */
max.mNext = max.mPrev = max;
min.mChild = mergeLists(min.mChild, max);
/* Reparent max appropriately. */
max.mParent = min;
/* Clear max's mark, since it can now lose another child. */
max.mIsMarked = false;
/* Increase min's degree; it now has another child. */
++min.mDegree;
/* Continue merging this tree. */
curr = min;
}
/* Update the global min based on this node. Note that we compare
* for <= instead of < here. That's because if we just did a
* reparent operation that merged two different trees of equal
* priority, we need to make sure that the min pointer points to
* the root-level one.
*/
if (curr.mPriority <= mMin.mPriority) mMin = curr;
}
return minElem;
}
/**
* Decreases the key of the specified element to the new priority. If the
* new priority is greater than the old priority, this function throws an
* IllegalArgumentException. The new priority must be a finite double,
* so you cannot set the priority to be NaN, or +/- infinity. Doing
* so also throws an IllegalArgumentException.
*
* It is assumed that the entry belongs in this heap. For efficiency
* reasons, this is not checked at runtime.
*
* @param entry The element whose priority should be decreased.
* @param newPriority The new priority to associate with this entry.
* @throws IllegalArgumentException If the new priority exceeds the old
* priority, or if the argument is not a finite double.
*/
public void decreaseKey(Entry<T> entry, double newPriority) {
checkPriority(newPriority);
if (newPriority > entry.mPriority)
throw new IllegalArgumentException("New priority exceeds old.");
/* Forward this to a helper function. */
decreaseKeyUnchecked(entry, newPriority);
}
/**
* Deletes this Entry from the Fibonacci heap that contains it.
*
* It is assumed that the entry belongs in this heap. For efficiency
* reasons, this is not checked at runtime.
*
* @param entry The entry to delete.
*/
public void delete(Entry<T> entry) {
/* Use decreaseKey to drop the entry's key to -infinity. This will
* guarantee that the node is cut and set to the global minimum.
*/
decreaseKeyUnchecked(entry, Double.NEGATIVE_INFINITY);
/* Call dequeueMin to remove it. */
dequeueMin();
}
/**
* Utility function which, given a user-specified priority, checks whether
* it's a valid double and throws an IllegalArgumentException otherwise.
*
* @param priority The user's specified priority.
* @throws IllegalArgumentException If it is not valid.
*/
private void checkPriority(double priority) {
if (Double.isNaN(priority))
throw new IllegalArgumentException(priority + " is invalid.");
}
/**
* Utility function which, given two pointers into disjoint circularly-
* linked lists, merges the two lists together into one circularly-linked
* list in O(1) time. Because the lists may be empty, the return value
* is the only pointer that's guaranteed to be to an element of the
* resulting list.
*
* This function assumes that one and two are the minimum elements of the
* lists they are in, and returns a pointer to whichever is smaller. If
* this condition does not hold, the return value is some arbitrary pointer
* into the doubly-linked list.
*
* @param one A pointer into one of the two linked lists.
* @param two A pointer into the other of the two linked lists.
* @return A pointer to the smallest element of the resulting list.
*/
private static <T> Entry<T> mergeLists(Entry<T> one, Entry<T> two) {
/* There are four cases depending on whether the lists are null or not.
* We consider each separately.
*/
if (one == null && two == null) { // Both null, resulting list is null.
return null;
}
else if (one != null && two == null) { // Two is null, result is one.
return one;
}
else if (one == null && two != null) { // One is null, result is two.
return two;
}
else { // Both non-null; actually do the splice.
/* This is actually not as easy as it seems. The idea is that we'll
* have two lists that look like this:
*
* +----+ +----+ +----+
* | |--N->|one |--N->| |
* | |<-P--| |<-P--| |
* +----+ +----+ +----+
*
*
* +----+ +----+ +----+
* | |--N->|two |--N->| |
* | |<-P--| |<-P--| |
* +----+ +----+ +----+
*
* And we want to relink everything to get
*
* +----+ +----+ +----+---+
* | |--N->|one | | | |
* | |<-P--| | | |<+ |
* +----+ +----+<-\ +----+ | |
* \ P | |
* N \ N |
* +----+ +----+ \->+----+ | |
* | |--N->|two | | | | |
* | |<-P--| | | | | P
* +----+ +----+ +----+ | |
* ^ | | |
* | +-------------+ |
* +-----------------+
*
*/
Entry<T> oneNext = one.mNext; // Cache this since we're about to overwrite it.
one.mNext = two.mNext;
one.mNext.mPrev = one;
two.mNext = oneNext;
two.mNext.mPrev = two;
/* Return a pointer to whichever's smaller. */
return one.mPriority < two.mPriority? one : two;
}
}
/**
* Decreases the key of a node in the tree without doing any checking to ensure
* that the new priority is valid.
*
* @param entry The node whose key should be decreased.
* @param priority The node's new priority.
*/
private void decreaseKeyUnchecked(Entry<T> entry, double priority) {
/* First, change the node's priority. */
entry.mPriority = priority;
/* If the node no longer has a higher priority than its parent, cut it.
* Note that this also means that if we try to run a delete operation
* that decreases the key to -infinity, it's guaranteed to cut the node
* from its parent.
*/
if (entry.mParent != null && entry.mPriority <= entry.mParent.mPriority)
cutNode(entry);
/* If our new value is the new min, mark it as such. Note that if we
* ended up decreasing the key in a way that ties the current minimum
* priority, this will change the min accordingly.
*/
if (entry.mPriority <= mMin.mPriority)
mMin = entry;
}
/**
* Cuts a node from its parent. If the parent was already marked, recursively
* cuts that node from its parent as well.
*
* @param entry The node to cut from its parent.
*/
private void cutNode(Entry<T> entry) {
/* Begin by clearing the node's mark, since we just cut it. */
entry.mIsMarked = false;
/* Base case: If the node has no parent, we're done. */
if (entry.mParent == null) return;
/* Rewire the node's siblings around it, if it has any siblings. */
if (entry.mNext != entry) { // Has siblings
entry.mNext.mPrev = entry.mPrev;
entry.mPrev.mNext = entry.mNext;
}
/* If the node is the one identified by its parent as its child,
* we need to rewrite that pointer to point to some arbitrary other
* child.
*/
if (entry.mParent.mChild == entry) {
/* If there are any other children, pick one of them arbitrarily. */
if (entry.mNext != entry) {
entry.mParent.mChild = entry.mNext;
}
/* Otherwise, there aren't any children left and we should clear the
* pointer and drop the node's degree.
*/
else {
entry.mParent.mChild = null;
}
}
/* Decrease the degree of the parent, since it just lost a child. */
--entry.mParent.mDegree;
/* Splice this tree into the root list by converting it to a singleton
* and invoking the merge subroutine.
*/
entry.mPrev = entry.mNext = entry;
mMin = mergeLists(mMin, entry);
/* Mark the parent and recursively cut it if it's already been
* marked.
*/
if (entry.mParent.mIsMarked)
cutNode(entry.mParent);
else
entry.mParent.mIsMarked = true;
/* Clear the relocated node's parent; it's now a root. */
entry.mParent = null;
}
public static class Node {
/**
* first child node
*/
int indice;
Node m_child;
/**
* left sibling node
*/
Node m_left;
/**
* parent node
*/
Node m_parent;
/**
* right sibling node
*/
Node m_right;
/**
* true if this node has had a child removed since this node was added
* to its parent
*/
boolean m_mark;
/**
* key value for this node
*/
int m_key;
/**
* number of children of this node (does not count grandchildren)
*/
int m_degree;
/**
* Default constructor. Initializes the right and left pointers,
* making this a circular doubly-linked list.
*
* @param key initial key for node
*/
public Node() {}
public Node(int key, int ind) {
m_right = this;
m_left = this;
m_key = key;
indice=ind;
}
/**
* Obtain the key for this node.
*
* @return the key
*/
public final int getKey() {
return m_key;
}
public final int getindice(){
return indice;
}
/**
* Return the string representation of this object.
*
* @return string representing this object
*/
public String toString() {
if (true) {
return Double.toString(m_key);
} else {
StringBuffer buf = new StringBuffer();
buf.append("Node=[parent = ");
if (m_parent != null) {
buf.append(Double.toString(m_parent.m_key));
} else {
buf.append("---");
}
buf.append(", key = ");
buf.append(Double.toString(m_key));
buf.append(", degree = ");
buf.append(Integer.toString(m_degree));
buf.append(", right = ");
if (m_right != null) {
buf.append(Double.toString(m_right.m_key));
} else {
buf.append("---");
}
buf.append(", left = ");
if (m_left != null) {
buf.append(Double.toString(m_left.m_key));
} else {
buf.append("---");
}
buf.append(", child = ");
if (m_child != null) {
buf.append(Double.toString(m_child.m_key));
} else {
buf.append("---");
}
buf.append(']');
return buf.toString();
}
}
// toString
}
} |
Partager