[Note: The first version of this answer was incorrect; the comments refer to the incorrect version.]
I'll assume that the parabolas all open downward as in the diagram; if they don't, things might be more complicated. I'll take $y$ to increase downward to simplify things.
A parabola is the locus of points at equal distance from a point (the focus) and a line (the directrix). In the present case, all directrices are horizontal. If we weight the distance from the focus by adding the $y$ coordinate of the directrix, we can regard the parabola as the locus of points where this weighted distance from the focus is equal to the $y$ coordinate of the point. Above the parabola, the weighted distance from the focus is greater, and below the parabola, the $y$ coordinate is greater. For a point on the upper envelope, the weighted distance from the focus of the parabola forming the envelope is equal to the $y$ coordinate of the point, and the weighted distances from all other foci are less than or equal to this $y$ coordinate. Thus, if we form the additively weighted Voronoi diagram of the foci, the parabolic segments forming the upper envelope lie in the Voronoi regions of the corresponding foci.
It follows that the intersections at which the upper envelope switches from one parabola to another lie on edges of the weighted Voronoi diagram. The weighted Voronoi diagram can be computed in $O(n\log n)$ time, for instance using Fortune's algorithm; the modification for the additively weighted case is straightforward and is described in the original paper (Section 4). Since the weighted Voronoi diagram is a planar graph with minimal vertex degree $3$ and $n$ faces, Euler's formula implies that it has $O(n)$ edges. Thus, the upper envelope can be constructed in $O(n\log n)$ time by computing the weighted Voronoi diagram, finding the intersections of parabolas whose Voronoi regions share an edge, ordering the intersections according to their $x$ coordinates and traversing them from left to right to determine at which of them the envelope switches to a different parabola.
Also see these notes for a discussion of the relationship between the upper/lower envelope of a set of parabolas and a Voronoi diagram.